[ZODB-Dev] Iterating through a B-Tree

[Stefan H. Holek]

Hi Martin!

It seems that if the data objects are already in memory, you will *lose* 
time on the list conversion.

Here are some tests I wrote to compare the performance of different mapping 
types (Python dict, PersistentMapping, and OOBTree)

Without list():

Testing 2000 items...
    Dict: 0.002
    PMap: 0.001
    Tree: 0.001
Testing 20000 items...
    Dict: 0.027
    PMap: 0.020
    Tree: 0.011
Testing 100000 items...
    Dict: 0.185
    PMap: 0.169
    Tree: 0.052
Testing 500000 items...
    Dict: 1.625
    PMap: 1.588
    Tree: 0.257
----------------------------------------------------------------------
Ran 4 tests in 8.910s

And with list():

Testing 2000 items...
    Dict: 0.002
    PMap: 0.001
    Tree: 0.001
Testing 20000 items...
    Dict: 0.028
    PMap: 0.022
    Tree: 0.023
Testing 100000 items...
    Dict: 0.265
    PMap: 0.198
    Tree: 0.205
Testing 500000 items...
    Dict: 1.548
    PMap: 1.645
    Tree: 1.916
----------------------------------------------------------------------
Ran 4 tests in 10.837s

Stefan


--On Dienstag, 12. August 2003 11:26 +0200 Gfeller Martin 
<Martin.Gfeller at comit.ch> wrote:

> I thought I let you know a timing surprise I had with iterating through
> all keys of a B-Tree:
>
> for k in list(conn.root.keys()):
> 	d = conn.root[k]
>
> is 8 times faster than the same loop without the conversion of the keys
> to a list, with conn.root being an OOBTree of length 47000. The timings
> on a 1 GHz Windows 2000 machine are 5.8 vs. 46.7 seconds.
>
> The actual difference seems to be in ZODB.FileStorage._load[615], which
> performs the physical read. My (naive) conjecture is that the list()
> forces all nodes to be read sequence, whereas without the list, a lot of
> file seeks are performed.
>
> Of course, iterating through a whole tree is not very common, but when it
> happens it is good to know that it can be speed up.

--
The time has come to start talking about whether the emperor is as well
dressed as we are supposed to think he is.               /Pete McBreen/