Boost logo

Boost :

From: Matt Doyle (mdoyle_at_[hidden])
Date: 2006-04-21 15:36:56


> [mailto:boost-bounces_at_[hidden]] On Behalf Of Thorsten Ottosen
Snip>
> > Performance is a concern given the recursive nature of the
> tree. I want write a test case parsing Usenet's group list.
> By it's nature it demands storage in a hierarchical tree
> where every node is both a leaf and a branch (like ptree :) ,
> it's a big list, and insertion / retrieval is mostly random.
> Hopefully I'll have time to do this before the review is over.
> >
Snip>
>
> Let me just say (as a review maanger) that such a test would
> be immensely useful (an an obvious candidate for inclusion
> with the library if it is accepted).
>
> I know it is an easy task, though.

Well, I finally have some performance results and, at to me at least, it
looks pretty good. I used a partial snap shot of the Usenet groups list
with 34767 records in it. I choose that particular file because I had
previously used it to compare performance between MFC's TreeView and a
handrolled tree using Berkley DB_TREE. TreeView parsed it in ~1200
seconds, Berkley at ~40 seconds, and now Ptree came in at 7.5 seconds.
To be fair, I didn't re-run the first two tests today, I just used my
results from previous tests so that may have been a slower computer
(~two years ago).

Anyway, of the 7.5 seconds 4.3 of it was I/O time so the library time to
build & populate the tree was 3.2 seconds, or 92uS per node. Iterating
the tree and writing it back out took 2.187 seconds, the average seek
time to search for a record was 16uS and the average time to search and
modify the same record was 125us.

SO all that being said, I want to re-affirm my vote that Ptree should be
accepted.

One thing aside though, I want to harp on the documentation again. While
the library was easy to use there were a few nuances that I had to
research along the way. I think that at a minimum we need to have some
concrete examples, starting at main(), showing the usage of each of the
parsers.

Attached is the test dataset and the test program if anyone else wants
to independently retest it.

Regards,
        Matt

Scanned by McAfee GroupShield {X3BTB534}






Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk