Tyler Camp: my custom implementation is the same as it was before, but instead of the nodes being allocated off the heap I just make a giant vector of blank nodes and pull new nodes out of it
Tyler Camp: it has the same structure, how I generate the nodes is just different
Allen Webster: right so there should be less cache misses
Tyler Camp: the tree's still there, the nodes that make up the tree are in contiguous memory
Tyler Camp: and maybe
Tyler Camp: I don't really know
Tyler Camp: I didn't really expect there to be much of a difference but I knew that it would be a possibility
Tyler Camp: since cache only goes up to about 16MB (lumping L1, L2, and L3 all together) there's no way that all of the relevant data could be stored in cache for comparison for either algorithm
Tyler Camp: EXCEPT
Tyler Camp: that fucking quicksort
Tyler Camp: right
Tyler Camp: all of my nodes are in contiguous memory, but they're not accessed linearly, they're accessed (almost) randomly
Tyler Camp: quicksort iterates directly over a group of elements, in this case all that memory is contiguous
Tyler Camp: and therefore it is the perfect candidate for acceleration via cache
Tyler Camp: my code, not so much
Allen Webster: wait...
Allen Webster: right
Allen Webster: I forgot how quicksort worked
Allen Webster: I wasn't thinking exactly correctly
Tyler Camp: roit
Tyler Camp: IIRC, it's along the lines of
Tyler Camp: pick some reasonable value; everything under that value is placed in one bin and everything over is placed in another bin
Tyler Camp: then, on each bin, repeat the process
Tyler Camp: it is essentially the same process as a binary tree's insertion, but with quicksort it iterates over the contents of an entire bin to do its comparisons
Allen Webster: ok I guess I was thinking correctly
Tyler Camp: the comparisons are against a single constant value, which is contained in memory
Tyler Camp: since the comparison is a single address and all other elements being referenced are contiguously aligned and linearly accessed, the cache can be adequately used to access data
Tyler Camp: with my code there's a comparison value that always changes (the current value being inserted) and the values it's being compared against are always changing since the node route to be taken for insertion will be different for each item
Allen Webster: anyway you're beating it in the <4000 range?
Tyler Camp: and past that is most likely approximately the point where all of the data can't be held in cache
Tyler Camp: well, it would require a lot more data to fill the cache, but at that 4000 point it's possible that more's being shoved into L3 than into L1 due to other processes running in the background, and quicksort can better make use of locally contiguous data. My application would be more likely to dip back and forth between L1, L3, and RAM, while quicksort would do spurts of L1 and then maybe some loading time from the RAM. (AFAIK.)