4 ms·

That was my thought too when I saw the 8192 number, but they deferred with "subject to further research". I wonder if you could crudely determine a number base

That was my thought too when I saw the 8192 number, but they deferred with "subject to further research". I wonder if you could crudely determine a number based on inspecting the size of the cache of the machine at runtime. I think the most impressive part about the whole thing is that the cache optimization flows naturally out of how the Trie is constructed rather than any voodoo on their part. (Since each string is handled once, rather than m times, where m is the string length, as in a pure radix sort.) It makes me wonder if the cache optimization aspect was foreseen or accidental.

gojomo 18y ago
I haven't looked closely at this 'burstsort', but have read previously about 'cache-oblivious' algorithms, that benefit consistently from memory caches whatever their size. (No tuning for different sizes required.) See discussion here: http://blogs.msdn.com/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx http://blogs.msdn.com/devdev/archive/2007/06/12/cache-oblivi...
- prakash 18y ago
  and this: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5...
- bd 18y ago
  See also this lecture on cache oblivious algorithms by Erik Demaine from MIT 6.046 "Introduction to Algorithms" course: "This is a particularly fun area, one dear to my heart because I've done a lot of research in this area. This is an area co-founded by Professor Leiserson. So, in fact, the first context in which I met Professor Leiserson was him giving a talk about cache oblivious algorithms at WADS '99 in Vancouver I think. Yeah, that has to be an odd year. So, I learned about cache oblivious algorithms then, started working in the area, and it's been a fun place to play. But this topic in some sense was also developed in the context of this class. I think there was one semester, probably also '98-'99 where all of the problem sets were about cache oblivious algorithms." http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed24.htm http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...

gojomo 18y ago

I haven't looked closely at this 'burstsort', but have read previously about 'cache-oblivious' algorithms, that benefit consistently from memory caches whatever their size. (No tuning for different sizes required.) See discussion here: http://blogs.msdn.com/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx http://blogs.msdn.com/devdev/archive/2007/06/12/cache-oblivi...

prakash 18y ago
and this: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5...
bd 18y ago
See also this lecture on cache oblivious algorithms by Erik Demaine from MIT 6.046 "Introduction to Algorithms" course: "This is a particularly fun area, one dear to my heart because I've done a lot of research in this area. This is an area co-founded by Professor Leiserson. So, in fact, the first context in which I met Professor Leiserson was him giving a talk about cache oblivious algorithms at WADS '99 in Vancouver I think. Yeah, that has to be an odd year. So, I learned about cache oblivious algorithms then, started working in the area, and it's been a fun place to play. But this topic in some sense was also developed in the context of this class. I think there was one semester, probably also '98-'99 where all of the problem sets were about cache oblivious algorithms." http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed24.htm http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...