* internal representation of recursive data types
@ 2005-11-02 16:44 Sebastian Egner
0 siblings, 0 replies; only message in thread
From: Sebastian Egner @ 2005-11-02 16:44 UTC (permalink / raw)
To: caml-list
[-- Attachment #1.1: Type: text/plain, Size: 6898 bytes --]
I have a few questions related to the internal representation of
recursive data types, having implications on the suitability of Ocaml
for highly efficient data structures.
One of the most efficient comparison-based search data structures in
the presence of memory hierachies (caching/paging) are (a,b)-trees.
In an (a,b)-tree, the number d of children of a non-root node is in {a..b}
and all leaves (search items) are at the same height of the tree. In case
the keys can be stored in the node itself (e.g. int or float), and
suitable
values for (a, b), the child to follow from a node can be determined
without
additional cache faults. In other words, by adapting parameters a and b
a favorable cache-aware data structure can be constructed.
After measuring performance and analyzing reasons, I found that the
favorable cache locality of the data structure is for a large part
destroyed
by the way the Ocaml (native code) compiler (on i386) chooses the internal
representation of the nodes and trees. To find out about this
quantitatively,
I then implemented (a,b)-trees again---this time working around the type
system (i.e. using Obj) in order to choose a more compact internal
representation of the trees. I will detail the layouts below.
It turns out that this made the program about 30% faster (and this also
means the result is only about a factor 3 slower than an optimized C++
implementation). This potential for optimization is a little too much to
ignore, but letting go of the type system is also not an attractive
option.
Now my question is
a) Is this effect known?
b) Is it considered relevant?
c) What were the design considerations that have lead to the design
of the current compiler in this regard?
Any ideas? I can provide the measurements and also the programs
(provided my employer, Philips Research Eindhoven, agrees to that)
for anyone to have a look for him- or herself in case there is any
interest.
Sebastian.
----------
1. Here is a piece of the 'good' Ocaml program defining the trees:
-- snip --
(* --- (a,b)-trees --- *)
assert ((!a >= 2) && (!b >= 2 * !a - 1));;
type ('key, 'value) item =
{ k: 'key;
mutable v: 'value
(* <<more fiels, e.g. linking>> *)
};;
type ('key, 'value) node =
{ mutable d: int; (* degree d in {2..b} *)
s: 'key array; (* splitters s[0..d-2] *)
c: ('key, 'value) tree array (* children c[0..d-1] *)
}
and ('key, 'value) tree =
| Empty (* the empty (a,b)-tree *)
| Item of ('key, 'value) item (* an item as leaf *)
| Node of ('key, 'value) node (* a splitting node *)
;;
type ('key, 'value) t =
{ mutable root: ('key, 'value) tree
(* <<more fields, e.g. size, parameters>> *)
};;
(* Invariants of the representation:
(1) The key of an Item reachable through child c[i], i in {0..d-1},
of a Node of degree d with splitters s[0..d-2] satisfies
s[i-1] < key <= s[i].
It is understood that s[-1] = -inf and s[d-1] = +inf,
but neither of these sentinel values is ever stored in s.
(2) All Items have the same depth (distance from the root).
(3) The degree d of a a non-root Node is in {a..b}, where
(a,b) are constant parameters with a >= 2, b >= 2 a - 1.
The degree of the root Node is in {2..b}.
(4) The arrays s and c of a Node have length b-1 and b.
(5) If the tree contains Empty then it is equal to Empty.
*)
-- snip --
If I analyzed it correctly, then these definitions result in the following
internal representation for trees and nodes
('key, 'value) tree =
Empty = (unboxed) int 0
Item of i = pointer to (heap-allocated) block with tag 0 and
single field i: .. item
Node of n = point to block with tag 1 and single field n: ('key,
'value) node
('key, 'value) node =
pointer to block with tag 0 and 3 fields for d, s, and c.
d = unboxed int
s, c = pointers to arrays of length b
------------
2. Here is a piece of the 'bad' Ocaml program defining the trees:
-- snip --
(* --- (a,b)-trees --- *)
assert ((!a >= 2) && (!b >= 2 * !a - 1));;
(* The internal representation of an (a,b)-tree is
empty: the unboxed integer 0,
item: an array [-1, key, value], or
node: an array [d, s[0..d-2], 0..0, c[0..d-1], 0..0]
where c[0] is located at position b.
Here
d : degree, unboxed integer in {2..b}
s[0..d-2] : splitters of type key
c[0..d-1] : children of type tree
Invariants of the representation:
(1) The key of an item reachable through child c[i], i in {0..d-1},
of a node of degree d with splitters s[0..d-2] satisfies
s[i-1] < key <= s[i].
It is understood that s[-1] = -inf and s[d-1] = +inf,
but neither of these sentinel values is ever stored in s.
(2) All items have the same depth (distance from the root).
(3) The degree d of a a non-root node is in {a..b}, where
(a,b) are constant parameters with a >= 2, b >= 2 a - 1.
The degree of the root node is in {2..b}.
(4) The arrays s and c of a node have length b-1 and b.
(5) If the tree contains empty then it is equal to empty.
Remark:
* The internal representation escapes the type system. This
is necessary in order to avoid intermediate pointers, e.g.
from a node record to the array of splitters, which would
otherwise produce lots of cache misses.
* We do not use the tag bits of heap-allocated blocks to
distinguish between items and nodes in order to avoid the
overhead of calling the C-function caml_obj_tag(). Instead
we store our own tag into field 0.
* We use only Obj.field and Obj.set_field to access the objects.
*)
type ('key, 'value) tree = Obj.t;;
type ('key, 'value) t =
{ mutable root: ('key, 'value) tree
(* <<more fields, e.g. size, parameters>> *)
};;
-- snip --
The internal representation of trees and nodes is like this:
('key, 'value) tree =
Empty = unboxed int 0
Item = pointer to block with first field the unboxed int -1
Node = pointer to node, i.e. block with first field unboxed int
>=0
node =
array of length 2 b consisting of degree d, d-1 splitters and
d pointers to child-trees, where d in {2..b}.
Remark: I chose not to use the tag bits of a block to distinguish items
and nodes because Obj.tag results in a C-call whereas getting the
degree-field results in a single machine instruction.
----
Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)
5656 AA Eindhoven
The Netherlands
tel: +31 40 27-43166
fax: +31 40 27-44004
email: sebastian.egner@philips.com
[-- Attachment #1.2: Type: text/html, Size: 13876 bytes --]
[-- Attachment #2: lookup.eps --]
[-- Type: application/octet-stream, Size: 13586 bytes --]
%!PS-Adobe-2.0
%%Title: lookup.eps
%%Creator: gnuplot 3.7 patchlevel 1
%%CreationDate: Wed Nov 2 14:59:20 2005
%%DocumentFonts: (atend)
%%BoundingBox: 50 50 554 770
%%Orientation: Landscape
%%Pages: (atend)
%%EndComments
/gnudict 256 dict def
gnudict begin
/Color false def
/Solid false def
/gnulinewidth 5.000 def
/userlinewidth gnulinewidth def
/vshift -46 def
/dl {10 mul} def
/hpt_ 31.5 def
/vpt_ 31.5 def
/hpt hpt_ def
/vpt vpt_ def
/M {moveto} bind def
/L {lineto} bind def
/R {rmoveto} bind def
/V {rlineto} bind def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke M
0 vshift R show } def
/Rshow { currentpoint stroke M
dup stringwidth pop neg vshift R show } def
/Cshow { currentpoint stroke M
dup stringwidth pop -2 div vshift R show } def
/UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def
/hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def
/DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
{pop pop pop Solid {pop []} if 0 setdash} ifelse } def
/BL { stroke userlinewidth 2 mul setlinewidth } def
/AL { stroke userlinewidth 2 div setlinewidth } def
/UL { dup gnulinewidth mul /userlinewidth exch def
10 mul /udl exch def } def
/PL { stroke userlinewidth setlinewidth } def
/LTb { BL [] 0 0 0 DL } def
/LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def
/LT0 { PL [] 1 0 0 DL } def
/LT1 { PL [4 dl 2 dl] 0 1 0 DL } def
/LT2 { PL [2 dl 3 dl] 0 0 1 DL } def
/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
/LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def
/Pnt { stroke [] 0 setdash
gsave 1 setlinecap M 0 0 V stroke grestore } def
/Dia { stroke [] 0 setdash 2 copy vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath stroke
Pnt } def
/Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V
currentpoint stroke M
hpt neg vpt neg R hpt2 0 V stroke
} def
/Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath stroke
Pnt } def
/Crs { stroke [] 0 setdash exch hpt sub exch vpt add M
hpt2 vpt2 neg V currentpoint stroke M
hpt2 neg 0 R hpt2 vpt2 V stroke } def
/TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath stroke
Pnt } def
/Star { 2 copy Pls Crs } def
/BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath fill } def
/TriUF { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath fill } def
/TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath stroke
Pnt } def
/TriDF { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath fill} def
/DiaF { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath fill } def
/Pent { stroke [] 0 setdash 2 copy gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath stroke grestore Pnt } def
/PentF { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath fill grestore } def
/Circle { stroke [] 0 setdash 2 copy
hpt 0 360 arc stroke Pnt } def
/CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def
/C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def
/C1 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc closepath fill
vpt 0 360 arc closepath } bind def
/C2 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C3 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C4 { BL [] 0 setdash 2 copy moveto
2 copy vpt 180 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C5 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc
2 copy moveto
2 copy vpt 180 270 arc closepath fill
vpt 0 360 arc } bind def
/C6 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C7 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C8 { BL [] 0 setdash 2 copy moveto
2 copy vpt 270 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C9 { BL [] 0 setdash 2 copy moveto
2 copy vpt 270 450 arc closepath fill
vpt 0 360 arc closepath } bind def
/C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill
2 copy moveto
2 copy vpt 90 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C11 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 180 arc closepath fill
2 copy moveto
2 copy vpt 270 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C12 { BL [] 0 setdash 2 copy moveto
2 copy vpt 180 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C13 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc closepath fill
2 copy moveto
2 copy vpt 180 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C14 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 360 arc closepath fill
vpt 0 360 arc } bind def
/C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto
neg 0 rlineto closepath } bind def
/Square { dup Rec } bind def
/Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def
/S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def
/S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def
/S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def
/S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill
exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill
2 copy vpt Square fill
Bsquare } bind def
/S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def
/S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill
Bsquare } bind def
/S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill
Bsquare } bind def
/S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def
/S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
2 copy vpt Square fill Bsquare } bind def
/S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def
/D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def
/D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def
/D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def
/D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def
/D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def
/D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def
/D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def
/D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def
/D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def
/D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def
/D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def
/D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def
/D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def
/D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def
/D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def
/D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def
/DiaE { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath stroke } def
/BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath stroke } def
/TriUE { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath stroke } def
/TriDE { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath stroke } def
/PentE { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath stroke grestore } def
/CircE { stroke [] 0 setdash
hpt 0 360 arc stroke } def
/Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def
/DiaW { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V Opaque stroke } def
/BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V Opaque stroke } def
/TriUW { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V Opaque stroke } def
/TriDW { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V Opaque stroke } def
/PentW { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
Opaque stroke grestore } def
/CircW { stroke [] 0 setdash
hpt 0 360 arc Opaque stroke } def
/BoxFill { gsave Rec 1 setgray fill grestore } def
end
%%EndProlog
%%Page: 1 1
gnudict begin
gsave
50 50 translate
0.100 0.100 scale
90 rotate
0 -5040 translate
0 setgray
newpath
(Helvetica) findfont 140 scalefont setfont
1.000 UL
LTb
798 420 M
63 0 V
6101 0 R
-63 0 V
714 420 M
(100) Rshow
798 1052 M
31 0 V
6133 0 R
-31 0 V
798 1422 M
31 0 V
6133 0 R
-31 0 V
798 1684 M
31 0 V
6133 0 R
-31 0 V
798 1888 M
31 0 V
6133 0 R
-31 0 V
798 2054 M
31 0 V
6133 0 R
-31 0 V
798 2195 M
31 0 V
6133 0 R
-31 0 V
798 2316 M
31 0 V
6133 0 R
-31 0 V
798 2424 M
31 0 V
6133 0 R
-31 0 V
798 2520 M
63 0 V
6101 0 R
-63 0 V
-6185 0 R
(1000) Rshow
798 3152 M
31 0 V
6133 0 R
-31 0 V
798 3522 M
31 0 V
6133 0 R
-31 0 V
798 3784 M
31 0 V
6133 0 R
-31 0 V
798 3988 M
31 0 V
6133 0 R
-31 0 V
798 4154 M
31 0 V
6133 0 R
-31 0 V
798 4295 M
31 0 V
6133 0 R
-31 0 V
798 4416 M
31 0 V
6133 0 R
-31 0 V
798 4524 M
31 0 V
6133 0 R
-31 0 V
798 4620 M
63 0 V
6101 0 R
-63 0 V
-6185 0 R
(10000) Rshow
798 420 M
0 63 V
0 4137 R
0 -63 V
798 280 M
(10) Cshow
1063 420 M
0 31 V
0 4169 R
0 -31 V
1413 420 M
0 31 V
0 4169 R
0 -31 V
1593 420 M
0 31 V
0 4169 R
0 -31 V
1679 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(100) Cshow
1944 420 M
0 31 V
0 4169 R
0 -31 V
2294 420 M
0 31 V
0 4169 R
0 -31 V
2474 420 M
0 31 V
0 4169 R
0 -31 V
2559 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(1000) Cshow
2824 420 M
0 31 V
0 4169 R
0 -31 V
3175 420 M
0 31 V
0 4169 R
0 -31 V
3354 420 M
0 31 V
0 4169 R
0 -31 V
3440 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(10000) Cshow
3705 420 M
0 31 V
0 4169 R
0 -31 V
4055 420 M
0 31 V
0 4169 R
0 -31 V
4235 420 M
0 31 V
0 4169 R
0 -31 V
4320 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(100000) Cshow
4585 420 M
0 31 V
0 4169 R
0 -31 V
4936 420 M
0 31 V
0 4169 R
0 -31 V
5116 420 M
0 31 V
0 4169 R
0 -31 V
5201 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(1e+06) Cshow
5466 420 M
0 31 V
0 4169 R
0 -31 V
5816 420 M
0 31 V
0 4169 R
0 -31 V
5996 420 M
0 31 V
0 4169 R
0 -31 V
6081 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(1e+07) Cshow
6347 420 M
0 31 V
0 4169 R
0 -31 V
6697 420 M
0 31 V
0 4169 R
0 -31 V
6877 420 M
0 31 V
0 4169 R
0 -31 V
6962 420 M
0 63 V
0 4137 R
0 -63 V
0 -4277 R
(1e+08) Cshow
1.000 UL
LTb
798 420 M
6164 0 V
0 4200 V
-6164 0 V
798 420 L
140 2520 M
currentpoint gsave translate 90 rotate 0 0 M
(ns/lookup \(cpu time\)) Cshow
grestore
3880 70 M
(n) Cshow
3880 4830 M
(lookup of random\(10^9\) in dict of size n) Cshow
1.000 UL
LT0
6311 4487 M
(Ab_tree1) Rshow
6395 4487 M
399 0 V
1243 904 M
265 9 V
265 74 V
265 39 V
265 109 V
265 96 V
265 114 V
265 72 V
265 109 V
266 337 V
265 282 V
265 220 V
265 155 V
265 148 V
265 98 V
265 94 V
265 119 V
265 122 V
265 106 V
265 94 V
265 397 V
1.000 UL
LT1
6311 4347 M
(Ab_tree2) Rshow
6395 4347 M
399 0 V
1243 872 M
265 30 V
265 99 V
265 54 V
265 32 V
265 103 V
265 31 V
265 67 V
265 110 V
266 186 V
265 316 V
265 241 V
265 160 V
265 138 V
265 111 V
265 97 V
265 104 V
265 157 V
265 84 V
265 99 V
265 423 V
1.000 UL
LT2
6311 4207 M
(Hashtbl) Rshow
6395 4207 M
399 0 V
1243 1049 M
265 -11 V
265 6 V
265 -2 V
265 7 V
265 -2 V
265 5 V
265 1 V
265 3 V
266 49 V
265 237 V
265 205 V
265 360 V
265 86 V
265 38 V
265 18 V
265 19 V
265 16 V
265 46 V
265 466 V
265 813 V
1.000 UL
LT3
6311 4067 M
(Map) Rshow
6395 4067 M
399 0 V
1243 1409 M
265 84 V
265 60 V
265 68 V
265 76 V
265 75 V
265 44 V
265 48 V
265 44 V
266 128 V
265 243 V
265 221 V
265 151 V
265 113 V
265 107 V
265 114 V
265 101 V
265 98 V
265 122 V
265 81 V
265 394 V
stroke
grestore
end
showpage
%%Trailer
%%DocumentFonts: Helvetica
%%Pages: 1
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2005-11-02 17:12 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-11-02 16:44 internal representation of recursive data types Sebastian Egner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).