On Tue, Oct 27, 2009 at 04:28:11PM -0400, John Crenshaw wrote: > "advantage" kind of depends. ULL is more specialized. You gain some > benefit, but also lose some as well. For example, consider what is > involved in doing a sorted insert into an ULL. On the other hand, you > can get all of the same locality benefit with a pool allocation > scheme. You don't reduce the pointer overhead this way, but that isn't > really much of an issue.
I don't know that you get the same locality benefit with pools: with a ULL there's fewer prev/next pointers to take up valuable cache space. The need to "pullup"/"breakup" a ULL at times is annoying, and to minimize you probably have to waste some space in order to amortize the cost. As you say, there's a trade-off. Many optimizations result in more complex, error-prone, brittle software. Wasting space is not much of a problem for cache locality, and if you keep the wasted space well under 50% you're ahead of plain lists in terms of memory footprint. So, ignoring code complexity, ULL seems like a likely win-win performance-wise. Even code complexity-wise, ULLs allow random access to be much faster than with plain linked lists, which means you're more likely to use random access, which means you probably win code complexity-wise too. Of course, once you start leaving room for additions in each chunk, ULLs start resembling B-trees, which, I think, is your point: might as well go whole-hog. > ULL requires less time to walk all nodes, but since you can't afford > to keep ULL sorted, there aren't a lot of scenarios where that saves I don't think it's true that you can't afford to keep it sorted, but you probably have to waste space if you want it sorted and allowing most random inserts to not require spills. Also, just because a chunk is full, or even all chunks are full, does not mean you must move lots of memory around: you can just insert a new chunk and move some entries from the neighboring ones into it, thus creating some breathing space for further additions (at the cost of space waste). Nico -- _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
