Data.Map improvement patch

[Milan Straka]

Hello,

Recently I was going through the Data.Set implementation and I was taken aback
by setting the parameter \delta to 4. The implementation is based on Adams'
bounded trees and uses ratio \alpha=2, in which case the paper clearly states
\delta must be at least 4.646 (which is written in the source file Set.hs
several lines above the assignment \delta=4; Map.hs uses \delta=5). So I read
that Adams' paper again and found out, that the analysis described there
contains two major mistakes [it is good to read the analysis from the paper 
now if you want to follow, pages 26 to 31].

1) The analysis assumes that just before the balancing rotation, the heavier
subtree of the unbalanced vertex was inserted to, i.e. the balance is ``off by
1''. But when the lighter subtree is deleted from, the balance is ``off by
\delta'', which is worse.  When taken into account, it results in equation
$\delta\le{n\over\alpha}+1$, which must hold for each positive integer n.

2) The cases of empty subtrees are not analysed. When considered, it follows
that for \alpha=2 a single rotation can restore balance only when \delta<5.
[tree with 1 left vertex and 5 right, delete the left one and voila...]

Right now I was puzzled why both Data.Set and Data.Map implementations seem to work.

*) Data.Set: The constraint from the paper \delta >= 4.646 comes from the
inequality $(1/\alpha) >= {\delta(1+{1\over n})+1\over\delta^2-1}$, which
must hold for each positive integer n. The worst case is n=1, which is
chosen in the paper. But when using n=2, the resulting constraint is
\delta>3.792. The remaining case n=1 can be solved by examining all
possible situations for \alpha<=2 and \delta=4, which all reveal to be
correctly balanced using a~single rotation. Also the new constraint
$\delta\le{n\over\alpha}+1$ can be satisfied for \alpha=2 and \delta=4 by
examining small cases separately.
The thing is the inequalities from the paper do not contain the floor function.
Sure, for general parameters it is difficult to handle, but for the specific
parameters the results are much better when truncation is taken into account.

*) Data.Map: The constraint \delta<5 for \alpha=2 is not possible to change
without changing the algorithm. But it turns out that the Data.Map
implementation performs the balancing rotations not when one subtree is more
than \delta times heavier than the other as described in the paper, but when
one subtree is at least \delta times heavier. So the Data.Map implementation
behaves like the analysed implementation with \delta just a bit smaller than 5.



Ok, so both 4 and 5 work for the implementation of Data.Map and Data.Set.
Which one is better? This parameter affects the height of a tree.  With
\delta=4 the worst case is 1:4, so the height is log_{5/4}n ~ 3.1 log_2 n.
With \delta=5 the height is log_{6/5}n ~ 3.8 log_2 n. In Haskell, lot of
operations must copy a whole path in a tree -- so a lower tree means less time
and memory needed. There are more rotations, but we have to construct new nodes
anyway, so one would expect minor advantage of \delta=4 over \delta=5.
It is difficult to measure these things in Haskell for me (just adding a
SPECIALIZE of increasing/decreasing heap size can change order of execution
time), but anyway, here are times of 50000 sequential inserts, then 800000
lookups and 50000 deletes (the source is attached for the freaks):
Data.Set with \delta=4  180 300 72
Data.Set with \delta=5  208 304 76
Data.Map with \delta=4  212 328 84
Data.Map with \delta=5  256 324 88
IntSet                   56 356 48
IntMap                   56 360 48



So I would suggest to change "delta = 5" to "delta = 4" in the Data.Map.hs
and leave "delta = 4" in the Data.Set.hs file. The darcs patch is included :)

Any comments are welcome,
Milan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: data.map.4.bench.tgz
Type: application/x-gtar
Size: 56140 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/libraries/attachments/20080421/8f3cd4e7/data.map.4.bench-0001.gtar
-------------- next part --------------
A non-text attachment was scrubbed...
Name: data.map.4.patch.gz
Type: application/octet-stream
Size: 22468 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/libraries/attachments/20080421/8f3cd4e7/data.map.4.patch-0001.obj