6 ms·
Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely rela
by jiggawatts 4y ago
Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf
A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way.
A way to think about it is that a CPU core is like a central point with "rings" of data arranged around it in a more-or-less a flat plane. The L1 cache is a tiny ring, then L2 is a bit further out physically and has a larger area, then L3 is even bigger and further away, etc... all the way out to permanent storage that's potentially across the building somewhere in a disk array.
In essence, as data size 'n' grows, the random access time grows as sqrt(n), because that's the radius of the growing circle with area 'n'.
Hence, a lot of algorithms that on paper have identical performance don't in reality, because one of the two may have an extra sqrt(n) factor in there.
This is why streaming and array-based data structures and algorithms tend to be faster than random-access, even if the latter is theoretically more efficient. So for example merge join is faster than nested loop join, even though they have the same performance in theory.
- vvanders 4y agoRealtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread. [1] https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323 https://www.amazon.com/Real-Time-Collision-Detection-Interac...
- trebcon 4y agoThe implicit grid data structure from there is a personal favorite of mine. I used it in a game once and it performed incredibly well for our use case. It's a bit too complicated to totally summarize here, but it uses a bit per object in the scene. Then bit-wise operations are used to perform quick set operations on objects. This data structure got me generally interested in algorithms that use bits for set operations. I found the Roaring Bitmap github page has a lot of useful information and references wrt this topic: https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
- phkahler 4y agoI spent a lot of time optimizing an octree for ray tracing. It is my favorite "spatial index" because it's the only one I know that can be dynamically updated and always results in the same structure for given object placement.
- SotCodeLaureate 4y agoI often recommend this book, RTCD, as a "better intro to data structures and algorithms" (sometimes as "the best"). The advice often falls on deaf ears, unfortunately.
- Gene_Parmesan 4y agoSeconding the RTCD recommendation. Handy code examples, and my favorite part is that the book is real-world-performance-conscious (hence the "real-time" in the title).
- thegeomaster 4y agoIt's a stellar book. I work on a commercial realtime physics engine, the "orange book" is practically required reading here.
- itamarst 4y agoDoes anyone actually use cache-oblivious data structure in practice? Not, like, "yes I know there's a cache I will write a datastructure for that", that's common, but specifically cache-oblivious data structures? People mention them a lot but I've never heard anyone say they actually used them.
- jiggawatts 4y agoTo an extent, the B-Tree data structure (and its variants) are cache oblivious. They smoothly improve in performance with more and more cache memory, and can scale down to just megabytes of cache over terabytes of disk. The issue is that the last tree level tends to break this model because with some caching models it is "all or nothing" and is the biggest chunk of the data by far. There are workarounds which make it more truly cache oblivious. How often this is used in production software? Who knows...
- jfim 4y agoThere are also Judy arrays: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array
- bruce343434 4y agoThis sounded promising but then I saw a performance benchmark [1] that was done on a pentium(!) with a very suboptimal hash table design compared to [2] and [3]. The Judy site itself [4] is full of phrases like "may be out of date", when the entire site was last updated in 2004. If it was already out of date in 2004... It seems that Judy arrays are just kind of a forgotten datastructure, and it doesn't look promising enough for me to put in effort to revive it. Maybe someone else will? [1] http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/ [2] https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... [3] https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/ https://probablydance.com/2018/05/28/a-new-fast-hash-table-i... [4] http://judy.sourceforge.net/ http://judy.sourceforge.net/
- School-Cotton 4y agoDo we mean different things by "merge join" and "nested loop join" ? For me "merge join" is O(n) (but requires the data to be sorted by key) whereas "nested loop join" is O(n^2).
- mountainreason 4y agoWouldn't you at least be looking at nlog(n) for the sort in the merge join?
- School-Cotton 4y agoYes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.
- mountainreason 4y agoYeah. I know. Why would the data already be sorted?
- School-Cotton 4y agoIn a database you might have already built an index on that data.
- cvoss 4y ago> In essence, as data size 'n' grows, the random access time grows as sqrt(n), because that's the radius of the growing circle with area 'n'. I was about to write a comment suggesting that if we made better use of three dimensional space in constructing our computers and data storage devices, we could get this extra latency factor down to the cube root of n. But then, I decided to imagine an absurdly large computer. For that, one has to take into account a curious fact in black hole physics: the radius of the event horizon is directly proportional to the mass, rather than, as one might expect, the cube root of the mass [1]. In other words, as your storage medium gets really _really_ big, you also have to spread it out thinner and thinner to keep it from collapsing. No fixed density is safe. So, in fact, I think the extra factor for latency in galactic data sets is neither the square root nor cube root, but n itself! [1] https://en.wikipedia.org/wiki/Schwarzschild_radius https://en.wikipedia.org/wiki/Schwarzschild_radius
- chriswarbo 4y agoThis series of blog posts explains this sqrt behaviour quite nicely, covering both theory (including black holes) and practice: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- 6510 4y agoIf its stored far away enough re-doing the calculation is faster. Depending on how much accuracy you need you might as well load a 2022-07-22 07:26:34 earth and have that guy on HN evaluate his thoughts all over again.
- samus 4y agoThe main difficulty with growing computing devices in three dimensions is cooling. All that heat has to be somehow carried away. It's already difficult with 2D devices. One would have to incorporate channels for cooling liquids into the design, which takes a bite out of the gains from 3D. https://www.anandtech.com/show/12454/analyzing-threadripper-cooling-big-base-cooling-wins https://www.anandtech.com/show/12454/analyzing-threadripper-...
- l33t2328 4y ago
- robotresearcher 4y agoDoing a decent job of analysis would include the sqrt(n) memory access factor. Asymptotic analysis ignores constant factors, not factors that depend on data size. It's not so much 'on paper' as 'I decided not to add a significant factor to my paper model'. Cache oblivious algorithms attempt to make the memory access term insignificant so you could continue to ignore it. They are super neat.
- physicsguy 4y agoI spent a long time looking at an algorithm for long range force calculations called the Fast Multipole Method which is O(N) and found that practically it couldn't compete against an O(N log N) method we used that involved FFTs because the coefficient was so large that you'd need to simulate systems way bigger than is feasible in order for it to pay off because of cache locality, etc.
- xigoi 4y agohttps://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
- mmorse1217 4y agoThis implementation and associated paper improve the cache locality to make the algorithm more competitive https://github.com/dmalhotra/pvfmm https://github.com/dmalhotra/pvfmm They compare solving toy problems with different methods here https://arxiv.org/pdf/1408.6497.pdf https://arxiv.org/pdf/1408.6497.pdf But as you mention, this is just fiddling with constants, and it still may be too costly for your problem
- jsmith45 4y agoHonestly, that is not too uncommon. For top level algorithm choice analysis, "rounding" O(log(n)) to O(1), and O(n*log(n)) to O(n), is often pretty reasonable for algorithm comparison, even though it is strictly incorrect. It is not uncommon for a simple O(n*log(n)) algorithm to beat out a more complex O(n) algorithm for realistic data sizes. If you "round" them to both O(n), then picking the simpler algorithm because the obvious choice, and can easily turn out to have better perf.
- physicsguy 4y agoTo be fair, in the general case (particles placed in arbitrary positions), it worked very well. The issue was that in the area of electromagnetics I worked on at the time, we make an assumption about things being placed on a regular grid, and that allows you to do the force calculation by convolving a kernel with the charges/dipole strength in Fourier space.
- robalni 4y agoI was experimenting a while ago with something that I think is related to this. If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this: for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { do_something(arr[i], arr[j]); } } When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i. I thought that a better algorithm might do all possible comparisons inside the first block of memory before accessing any other memory. I wanted this to work independently of the size of cache lines or pages, so the solution would be that for each power of 2, we access all items in a position lower than that power of 2 before moving to the second half of the next power of 2. This means that we need to first compare indexes (0,0) and then (1,0),(1,1),(0,1) and then all pairs of {0,1,2,3} that haven't yet been compared and so on. It turns out that the sequence (0,0),(1,0),(1,1),(0,1) that we went through (bottom-left, bottom-right, top-right, top-left in a coordinate system) can be recursively repeated by assuming that the whole sequence that we have done so far is the first item in the next iteration of the same sequence. So the next step is to do (0,0),(1,0),(1,1),(0,1) again (but backwards this time) starting on the (2,0) block so it becomes (2,1),(3,1),(3,0),(2,0) and then we do it again starting on the (2,2) block and then on the (0,2) block. Now we have done a new complete block that we can repeat again starting on the (4,0) block and then (4,4) and then (0,4). Then we continue like this through the whole array. As you can see, every time we move, only one bit in one index number is changed. What we have here is actually two halves of a gray code that is counting up, half of it in the x coordinate and the other half in y. This means that we can iterate through the whole array in the described way by making only one loop that goes up to the square of the size and then we get the two indexes (x and y) by calculating the gray code of i and then de-interleaving the result so that bits 0,2,4... make the x coordinate and bits 1,3,5... make y. Then we compare indexes x and y: for (int i = 0; i < size * size; i++) { get_gray_xy(i, &x, &y); do_something(arr[x], arr[y]); } The result of all this was that the number of cache line/page switches went down by orders of magnitude but the algorithm didn't get faster. This is probably for two reasons: incremental linear memory access is very fast on modern hardware and calculating the gray code and all that added an overhead.
- samsquire 4y ago
- JackFr 4y agoI saw an amazing presentation on Purely Functional Data structures with a really approachable and understandable proof on ho w a particular structure was asymptotically constant or linear time (I believe), and then followed up by saying that in practice none of it worked as well as a mutable version because of caching and data locality. Oh well.
- qwrshr 4y agoIs there by any chance a publicly available recording of this presentation on purely functional data structures?
- JackFr 4y agoNE Scala Symposium Feb 2011 http://vimeo.com/20262239 http://vimeo.com/20262239 Extreme Cleverness: Functional Data Structures in Scala or maybe http://vimeo.com/20293743 http://vimeo.com/20293743 The Guerrilla Guide to Pure Functional Programming (At work, so I can't check the video) Both of them were excellent speakers
- cratermoon 4y ago> the increasing latency/cost of data access as the data size grows Latency Numbers Everyone Should Know https://static.googleusercontent.com/media/sre.google/en//static/pdf/rule-of-thumb-latency-numbers-letter.pdf https://static.googleusercontent.com/media/sre.google/en//st...
- NavinF 4y agoThe ratios are mostly correct, but the absolute numbers are wrong these days. For example, memory read latency can be 45ns (not 100) with a decent DDR4 kit and data center latency can be 10us (not 500us) with infiniband.
- chakkepolja 4y agohttp://queue.acm.org/detail.cfm?id=1563874 http://queue.acm.org/detail.cfm?id=1563874 http://deliveryimages.acm.org/10.1145/1570000/1563874/jacobs3.jpg http://deliveryimages.acm.org/10.1145/1570000/1563874/jacobs...