Re: [Boost-users] How to improve property_tree performance

Subject: Re: [Boost-users] How to improve property_tree performance
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2010-10-18 09:59:07

On 18.10.2010, at 14:38, Thorsten Ottosen wrote:

>> I've never done a performance analysis of PTree (I hardly have time to
>> get the docs up to date with the actual library), so I don't know what
>> is fast and what is slow. PTree is definitely not a fast library. I have
>> some ideas about how to make it faster, but that would take essentially
>> a reimplementation of the ptree class.
> 
> ptree uses std::list internally, right? I think it would be worth to use e.g. boost::ptr_deque or boost::ptr_vector (or a similar scheme) to reduce the number of heap allocations somewhat.

No. It used to do that, but when I took the library over, I realized that the documentation made complexity guarantees for find() that it couldn't keep (and also that it created a std::list of an undefined type, which is technically undefined), so I reimplemented it using a multi-index container and some seriously ugly data hiding to delay the container definition to where the ptree type is complete.

I've played with the idea of creating the index-by-name lazily, and indeed use a ptr_vector to hold the sequence of elements. I think it would improve performance, but as I said, that would be essentially another reimplementation. Also, last time I looked, intrusive containers (for the index) didn't like incomplete member types, which is a real pity. Also, the library currently makes iterator validity guarantees that would be rather tricky, if not impossible, to keep for containers other than list and multi_index.

I still might do it, if I ever find the time. But don't count on it.

Sebastian