[m-dev.] new library module

Zoltan Somogyi zs at cs.mu.OZ.AU
Tue Mar 30 16:06:25 AEST 1999


> Anyone want to review it? (Before you ask, I haven't checked the
> performance impact when it replaces tree234 in map; the bootcheck I need
> for that is still going.)

I have now done the performance tests. The results show that 23 trees
are very slightly slower than 234 trees.

::::::::::::::
/mount/munkora/staff/zs/tmp/TIME_TREE23
::::::::::::::
67.962u 1.327s 1:25.13 81.3%    9+465k 24+149io 0pf+0w
67.764u 1.344s 1:25.95 80.3%    9+465k 24+149io 0pf+0w
68.079u 1.455s 1:12.65 95.6%    9+465k 24+149io 0pf+0w
68.504u 1.284s 1:11.91 97.0%    9+466k 4+150io 0pf+0w
::::::::::::::
/mount/munkora/staff/zs/tmp/TIME_TREE234
::::::::::::::
67.786u 1.506s 1:25.11 81.4%    9+449k 686+149io 418pf+0w
67.574u 1.232s 1:12.03 95.5%    9+450k 4+149io 0pf+0w
67.704u 1.323s 1:14.11 93.1%    9+449k 4+149io 0pf+0w
67.685u 1.304s 1:13.17 94.2%    9+450k 4+149io 0pf+0w

The code for insertions into 23 trees sometimes construct a unique cell
that Simon's structure reuse optimization should be able to reuse. The code
for inserting into 234 trees has no such opportunity. Therefore 23 trees may
become slightly more competitive in the future, although I doubt it will be
enough to make them faster than 234 trees.

> If you are going to do performance testing, I suggest that you look at
> rbtree as well.

Unfortunately, rbtree.m does not implement all the operations map.m needs.

Zoltan.



More information about the developers mailing list