Nicolas Lehuen's Weblog

Here it is !

What’s new : after reading Scott Meyers’s Effective STL, I finally saw the light and was able to squeeze a little bit more of performance, eventually getting faster using std::vector than what I got with my hand-written vector-like class. This cancels what I’ve written about std::vector. This shows that STL is a very powerful library, but also that it makes it easy to shoot yourself in the foot if you don’t use it correctly. It also shows that Scott Meyers’s books are much needed if you want to write, well, effective C++ (wink, wink, nudge, nudge).

As an extra bonus, the new implementation of the pack() method now really packs the tree. Removed nodes were not, and still aren’t, removed from the tree. Instead, they are kept for later reuse, so that if a new node is later needed, a removed node can be used instead. This saves a lot of time and memory if you have a dirty phase in your computations where you have to add and remove a lot of nodes. Once the war is over, however, those empty nodes were left in memory, even if the chance of them being reused dropped to zero. Now, when you pack() the tree, those nodes are removed (the tree nodes get defragmented) and the final memory buffer gets shrinked down to the minimum.

It’s somewhat comparable to what you do when you « compress » a database (vacuum it in PostgreSQL, compress it in Access or Microsoft SQL Server, optimize it in MySQL, I guess). It has been quite interesting to find this algorithm as I guess it’ll be pretty useful when disk storage will come into play.

I’m leaving for Barcelona tomorrow night to spend New Year’s Eve with some friends over there. So I won’t update this blog till then… So let me give you readers (all 3 of them) my best wishes for 2006 !