Nicolas Lehuen's Weblog

It's been a few months since my last release of an official version of pytst. Seeing that someone in Japan uses it made me have a look at the project once again. If I remember correctly, the latest evolutions where mostly refactorings in the hope that I could come up with on-disk storage of the tree, plus a few experiment on my full text indexing system based on the TST (which I won't release yet). So, I'm releasing the latest version, having made sure that it compiled correctly for Python 2.3, 2.4 and 2.5 on Win32 and Ubuntu Linux (I only tested Python 2.4 on Linux)

I've been pretty busy lately, what with the fact that I now have TWO regular jobs (both theoretically being at 50%) : I'm still CTO at The CRM Company, but I am now VP Product & Marketing (and developer ) at Yoono on top of that. Interesting times...

My work on TSTs has been used at Yoono ; my friend (and now boss) Laurent Quérel and I have gone a bit further with TSTs and came up with a kind of TST which can store multiple characters per tree node. Any time some part of a prefix can be shared by multiple keys, the part is fully stored in the node and not duplicated, thus saving a lot of unnecessary nodes and navigation. Though it surely exists somewhere, we haven't seen it anywhere else, so we decided to simply call this kind of TST a CompactTST. What's interesting in this TST is that it has a very low memory overhead : the indexing structure only adds 10% to the bulk volume of the data (string key + integer value in our case) it contains.

As I've wrote previously, my work on Yoono made me switch back to writing Java. Hence, the CompactTST is written in Java, but with a low-level edge : like I've did in C++ for pytst, we didn't want to build a Java instance per tree node. Our solution is a bit rough but it does work perfectly : we store nodes in a byte[], manually managing the layout of nodes and the storage of their data in the byte array. The result is pretty fast, very compact and the GC doesn't work at all.

This gave me the idea of reusing this method to store a big number of objects in memory. Now that we have 64 bit servers with 8 Gb memory, why not make the most of it ? So currently I'm on my way to storing tens of millions of objects in memory through my own memory allocator system, implemented on top of multiple byte arrays, without any problem caused by memory or GC overhead. Of course, this means that I can't rely on the GC anymore, but it's the whole point anyway. We now have a way to store millions of String, int, List<Integer> and List<String> in an efficient way. I'm sure die hard Java developers would cringe at what we are doing, but it's fun and worthwhile.

I'm still planning on writing pytst 2.0, this time with a proper storage layer which will make me able to switch from memory-based to disk-based storage. Now that we have a neat CompactTST in Java, I'll take the opportunity of porting the algorithms to C++ at the same time. It's only a matter of finding the time to do it, which is easier said than done...

This release uses SWIG 1.3.28. The latest version of SWIG brings huge improvements in performance, bringing it on par with Boost.Python according to my crude benchmarks. The advantage of SWIG is that it is much more easy to build, being supported by the distutils package (though I had problems with C++ support). You don't have to learn a new set of building tricks like when using Boost. So, it seems that SWIG is back in the game !

Big thanks to the SWIG development team !

Update : Using the -O optimizing option in SWIG 1.3.28 yields even better performance, thus making the SWIG wrapper effectvely faster than the Boost.Python one. I don't know what happens under the hood though, but at least I can read the generated code, contrary to what happens in Boost. My unit and torture tests behave as before, so it seems everything is OK ! Great !

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 !

After a few hours of struggle, I managed to build a Python binding of tst 0.97 using Boost.Python. The results are great, my (unscientific) performance benchmarks show a 25% performance improvement over the version using SWIG. This is not surprising since SWIG takes your C++ class, builds a flat-view of your class as a set of C functions, then build a Python wrapper around this set of functions.

A few remarks, though :

• Boost and Boost.Python is a whole new world to discover. If you want things to remain a bit under your control, you HAVE to forget about make, nmake or Visual Studio and learn a new project building tool, bjam. It does not go without its surprises (for example, as a hint, don't name the top-level directory of your project "boost". It will confuse bjam.). Also, I'm a bit worried about the "buildability" of pytst. Up until now, it could be built using python setup.py install, now you have to use a whole new toolset.
• What's cool is that the .pyd extension does not need a .py module. What's less cool is that it need a runtime DLL named boost_python.dll (but it is built along with your own extension).
• Boost.Python is quite clever, but it does not understand the char* string, int string_length idiom. SWIG does not, either, but at least you can teach it using SWIG templates. To work around this I had to use std::basic_string which is recognized by Boost and mapped to a Python str type. Anyway, I have to change tst so that it uses basic_strings instead of this idiom which is hackish and not supported by Delphi, either. Because, you know, the Yoono client is developed in Delphi (hint, hint).
• Boost.Python is very clean and cool, using hardcore C++ meta-programming constructs. The problem is that you don't get to know what is the result of all this magic. There is no code generation, since everything is done through meta-programming. This is a bit disturbing because you have to have an absolute trust in Boost.Python and hope it always does The Right Thing™.
• Since it uses hardcore C++ meta-programming, I strongly advise you to refresh your knowledge on C++ templates. On the one hand, the mapping code is pretty simple and straightforward (see below), but on the other hand, as soon as you dwelve a bit further in the tricks and trades of overloading pure virtual functions in Python, things get quite hairy (see below, too).

To sum up : what's cool with Boost.Python ? Performance, and code like that :

   class_< TST >("TST")
        .def("put",&TST::put)
        .def("__setitem__",&TST::put)
        
        .def("get",&TST::get)
        .def("__getitem__",&TST::get)
        
        .def("get_or_build",&TST::get_or_build)
        
        .def("remove",&TST::remove)

        .def("write",&TST::write)
        .def("read",&TST::read)

        .def("walk",&TST::walk)

        .def("close_match",&TST::close_match)
        .def("prefix_match",&TST::prefix_match)

        .def("pack",&TST::pack)
    ;

What's less cool is code like that :

template <class S, class T> class string_action_wrapper :
        public action<S,T>,
        public wrapper< action<S,T> > {
    public:
        void perform(S* string,int string_length,int remaining_distance,T data) {
            return call<void,std::basic_string<S>,int,T>(
                this->get_override("perform").ptr(),
                std::basic_string<S>(string,string_length),
                remaining_distance,
                data
            );
        }
        
        T result() {
            return call<T>(this->get_override("result").ptr());
        }
};

But who cares as long as we get some performance ! Mu-HAHAHAHA ! Err, sorry...

OK, I should have done this waaaaaaay before. Anyway, I've made those changes to the API :

• TST.almost(string,maximum_distance,filter,action) has been renamed to TST.close_match(string,maximum_distance,filter,action)
• TST.common_prefix(string,filter,action) has been renamed to TST.prefix_match(string,filter,action)
• walk now takes an optional parameter : TST.walk(filter,action,start=None). If start is provided, the walk starts there, giving you all entries in the tree whose key begins with the given string.
• The NullFilter class is removed, since it is useless. Just pass None if you don't want any filter.

I'm sorry if the migration poses any problems, all the more so that I'm the first who has to refactor some code . The method names were very bad, common_prefix was especially confusing. This should be the last API change, the 1.0 version is close now.

Download pytst 0.96 here.

Nothing much new this time, I'm now using setuptools to package the application into an egg file (see EasyInstall for the user's point of view). I have also sneakily used my access on one of the Apache foundation's FreeBSD servers to check whether pytst can be built and used on another platform than Win32. Everything seems OK :).

Download pytst 0.94 here.

I was trying to understand why my latest version of pytst (0.92) was 10% slower than the previous one (0.86). I have made three important changes between those two versions :

• I used my PythonReference class to ease the Python reference count management. I was fed up with having to manage Py_INCREF and Py_DECREF manually, so I decided to let the C++ compiler do the job itself, following the advice of Scott Meyers.
• I made a complete overhaul of the memory_storage class, which is the class that, well, manages the storage of the TST nodes in memory (my long term plan is to provide a file_storage class to be able to store and use the tree directly on the filesystem). I was feeling a bit silly to have implemented my own kind of std::vector implementation, so I wisely decided to use std::vector instead. After all, why reinvent the wheel ?
• The serialization system is now completely independent of the storage implementation. It's like a generic dump of the tree. This way, it will be possible to serialize a tst instance backed by a memory_storage and load it into a tst instance backed by a (not yet available) file_storage. Of course, this point is not related to the performance loss at all.

It turns out that when you use a profiler (I used the 15-days free evaluation of AQtime 4, which has everything I could dream of for a profiler, the first thing being that "it just works"), a lot of methods from std::vector are hotspots. Granted, this is in debug mode, so some code that should be inlined is not, but if a function is an hotspot when called, it has good chances of remaining an hotspot when inlined, don't you think ? Well, I've quickly reimplemented a std::vector-like behaviour right into memory_storage, and presto, I nearly get back my 10% percents of lost performance. Plus, the source code is not so much more complicated.

So, sometimes it's worth reinventing the wheel, especially for simple cases like that.

Anyway, those results are not especially surprising : the Microsoft implementation of std::vector::at (which was the most method that my code used the most) instantiates an iterator and uses the overloaded + operator, only to access a vector element ! I can't imagine how this could be more complicated. I don't know if this kind of convoluted way to do things is also found in other STL implementations, but it is a bit creepy...

Now, after the removal of std::vector, what's the top hotspot ? SWIG_Python_ConvertPtr ! Looks like SWIG will have to disappear... I'm really thinking about using PyCXX or Boost.Python.

It is very frustrating to have to fight against all those layers of foreign code, when all you want to do is optimize your own code ! Anyway, here comes pytst 0.93 !

Here, from a French compatriot ;-). This one implements tail compression, which is an important space optimisation for TSTs. I have not implemented it until now since some of the algorithms implemented in my TST (namely the close match algorithm) would become quite complicated. I'm still thinking about a way to do it efficiently...

Update: this is a TST implementation all right, but without Python bindings.