From: Bardur A. <sp...@sc...> - 2005-03-05 11:51:43
|
Hi all, Just for the heck of it I implemented the VList data structure described in http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200244.pdf I've only implemented the basic stuff needed to do some benchmarking, but if there is interest I might implement the rest of the List interface. There are two things to note about the implemenetation as it is: - It is not currently thread safe, but achieving thread safety should only require very minor modifications. - For small lists, a considerable amount of memory is wasted, but as the lists grow, the space consumed gets asymptotically closer to that of an array(!). A snapshot can be retrieved from http://www.imada.sdu.dk/~bardur/personal/programs/ocaml-vlist/ocaml-vlist-20050305.tar.bz2 The test results are quite interesting. On my Athlon64 3500+, with 2GB of memory, a couple of test runs yield: $ ./examples/test1.opt Benchmarks... 10000000 x VList.(::)... 1.05192 10000000 x List.(::)... 2.28799 50000 x VList.nth... 0.000813007 50000 x List.nth... 14.4831 50000 x VList.length... 0.00608492 50000 x List.length... 32.4571 10000000 x cdr(VList)... 0.176178 10000000 x cdr(VList)... 0.116828 $ ./examples/test1.opt Benchmarks... 10000000 x VList.(::)... 0.926367 10000000 x List.(::)... 2.01412 50000 x VList.nth... 0.00077486 50000 x List.nth... 12.8647 50000 x VList.length... 0.00628901 50000 x List.length... 32.2211 10000000 x cdr(VList)... 0.179661 10000000 x cdr(VList)... 0.131431 which looks quite good especially considering that it's 100% pure OCaml. Maybe a candidate for ExtLib? -- Bardur Arantsson <ba...@im...> <ba...@sc...> - What is it? The language? Or the nudity, hopefully...? David Letterman, 'The Late Show' |
From: Alain F. <Ala...@in...> - 2005-03-05 22:39:34
|
Hi, Bardur Arantsson wrote: > Just for the heck of it I implemented the VList data > structure described in > > http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200244.pdf Cute. > $ ./examples/test1.opt > Benchmarks... > 10000000 x VList.(::)... 1.05192 > 10000000 x List.(::)... 2.28799 > 50000 x VList.nth... 0.000813007 > 50000 x List.nth... 14.4831 > 50000 x VList.length... 0.00608492 > 50000 x List.length... 32.4571 > 10000000 x cdr(VList)... 0.176178 > 10000000 x cdr(VList)... 0.116828 (The last line is actually List.tl) I'm quite surprised that the slowdown for VList.tl is so small, considering it has to allocate a block. Isn't it the case that most of the time is actually spent in the loop itself, and no the tl operation ? The good thing is that iterators (fold, map, iter) can be implemented without allocating that much. The paper describes a way to represent a list with a single pointer, which would avoid allocating for the tl operation. I guess this cannot be easily implemented in OCaml, since it requires cooperation with the GC. Do you have any idea about it ? Also, I'm concerned with your Obj.magic to create dummy elements to fill the array. Are you sure it will work with vlists of floats ? Why don't you use the element you add (in ::) and an equivalent of Array.map (in map) ? (Array.map as it is would produce a different traversal order for the vlists) -- Alain |
From: Bardur A. <sp...@sc...> - 2005-03-05 23:18:26
|
Alain Frisch wrote: >> $ ./examples/test1.opt >> Benchmarks... >> 10000000 x VList.(::)... 1.05192 >> 10000000 x List.(::)... 2.28799 >> 50000 x VList.nth... 0.000813007 >> 50000 x List.nth... 14.4831 >> 50000 x VList.length... 0.00608492 >> 50000 x List.length... 32.4571 >> 10000000 x cdr(VList)... 0.176178 <== VList.tl >> 10000000 x cdr(VList)... 0.116828 <== List.tl > (corrections above, just to make it absolutely clear) > I'm quite surprised that the slowdown for VList.tl is so small, > considering it has to allocate a block. Isn't it the case that most of > the time is actually spent in the loop itself, and no the tl operation ? I guess that could be quite likely. > > The good thing is that iterators (fold, map, iter) can be implemented > without allocating that much. - iter doesn't need to allocate anything - fold doesn't need to allocate anything (I *think*... it may need a logarithmic number of 'pointers') - map of course needs to allocate data blocks, but by using blocks directly it avoids having to allocate lots of (temporary) pointers. > > The paper describes a way to represent a list with a single pointer, > which would avoid allocating for the tl operation. I guess this cannot > be easily implemented in OCaml, since it requires cooperation with the > GC. Do you have any idea about it ? I only briefly considered it, but if one were to do it in pure OCaml it would probably need more magic than I can pull off. :) > > Also, I'm concerned with your Obj.magic to create dummy elements to fill > the array. Are you sure it will work with vlists of floats ? A test with three elements suggests, yes. :) Aren't floats heap-allocated? I think it will work in general because a 'NULL' pointer made through Obj.magic will be at least as large as any non-heap object (and heap objects are of course pointed to, so that'll work too). > Why don't you use the element you add (in ::) and an equivalent of Array.map (in > map) ? (Array.map as it is would produce a different traversal order > for the vlists) I'm not sure I follow... Once you have a pointer into the list (ie. the parameter you're calling VList.map with) everything back from that point is read-only, so you don't to construct anything using (::)...?!? I'm also pretty sure the current VList.map does produce a result with the correct ordering. The resulting VLists are created as in e.g. |-------| --> |-------| --> |-------| -> (NIL) | l'[2] | | l'[5] | | l'[6] | | l'[1] | | l'[4] | l -> | l'[0] | | ..... | (Coincidentally the reason I'm not just calling Array.map, but actually traversing the array backwards (and copying each element individually), is that I want the *application* of the user's closure to be performed in-order as well... if their closure has side-effects this would be the natural way to expect things to work, although I haven't checked to see if List.map actually specifies this.) Cheers, -- Bardur Arantsson <ba...@im...> <ba...@sc...> - Thank God it landed in that smoking crater! Chief Clancy Wiggum, 'The Simpsons' |
From: Bardur A. <sp...@sc...> - 2005-03-05 23:31:07
|
Bardur Arantsson wrote: > Alain Frisch wrote: > I'm also pretty sure the current VList.map does produce a result with > the correct ordering. The resulting VLists are created as in e.g. > [--snip--] Of course I screwed up the indexes... that should have been |-------| --> |-------| --> |-------| -> (NIL) | l'[2] | | l'[4] | | l'[5] | | l'[1] | | l'[3] | l -> | l'[0] | | ..... | -- Bardur Arantsson <ba...@im...> <ba...@sc...> ... and that proves the base case. One down, infinitely many to go. |
From: Alain F. <Ala...@in...> - 2005-03-05 23:36:20
|
Bardur Arantsson wrote: >> Also, I'm concerned with your Obj.magic to create dummy elements to >> fill the array. Are you sure it will work with vlists of floats ? > > > A test with three elements suggests, yes. :) Aren't floats heap-allocated? Floats in float arrays are inlined. It might be possible to work with arrays of heap-allocated floats with the kind of magic you use, but I would not recommend to do that. > I think it will work in general because a 'NULL' pointer made through > Obj.magic will be at least as large as any non-heap object (and heap > objects are of course pointed to, so that'll work too). The NULL pointer is really the 0 integer (represented by 1 in memory). >> Why don't you use the element you add (in ::) and an equivalent of >> Array.map (in map) ? (Array.map as it is would produce a different >> traversal order >> for the vlists) > > > I'm not sure I follow... Once you have a pointer into the list (ie. the > parameter you're calling VList.map with) everything back from that point > is read-only, so you don't to construct anything using (::)...?!? I mean, instead of putting a dummy value (__NULL__ ()) when you allocate in new block in (::), you could use the first argument of (::) as the initializer for the array. And it has the correct type, by definition. So if you create vlists of floats, the arrays will end up being real arrays of floats (with inlined floats), not arrays of boxed floats. > I'm also pretty sure the current VList.map does produce a result with > the correct ordering. I don't claim the opposite. I just wanted to say that you could use the same implementation technique as for Array.map to get rid of the __NULL__ in VList.map, but Array.map by itself would give a wrong traversal order. Really, there is no need to use unsafe features here. Be on the safe side ! (and it will be more efficient for float vlists) Cheers, Alain |
From: Bardur A. <sp...@sc...> - 2005-03-05 23:58:30
|
Alain Frisch wrote: >>> Why don't you use the element you add (in ::) and an equivalent of >>> Array.map (in map) ? (Array.map as it is would produce a different >>> traversal order >>> for the vlists) >> >> I'm not sure I follow... Once you have a pointer into the list (ie. >> the parameter you're calling VList.map with) everything back from that >> point is read-only, so you don't to construct anything using (::)...?!? > > I mean, instead of putting a dummy value (__NULL__ ()) when you allocate > in new block in (::), you could use the first argument of (::) as the > initializer for the array. And it has the correct type, by definition. > So if you create vlists of floats, the arrays will end up being real > arrays of floats (with inlined floats), not arrays of boxed floats. Ah, got ya. I think there *might* be a problem with doing this. I don't remember the details right now, but I do remember being quite sure it was actually necessary to fill up using NULLs instead of copies. (Obviously it had something to do with the extra references causing objects to hang around for longer than necessary). Actually, I'm not so sure that it is actually necessary, right now. I'll examine it more closely tomorrow. > Really, there is no need to use unsafe features here. Be on the safe > side ! (and it will be more efficient for float vlists) Of course, I'd like to avoid them, but I was sure I needed the NULLs at the time of implementation... that may change tomorrow. :) Cheers, -- Bardur Arantsson <ba...@im...> <ba...@sc...> Thank you very little. |
From: Alain F. <Ala...@in...> - 2005-03-06 00:15:17
|
Bardur Arantsson wrote: > I think there *might* be a problem with doing this. I don't remember the > details right now, but I do remember being quite sure it was actually > necessary to fill up using NULLs instead of copies. (Obviously it had > something to do with the extra references causing objects to hang around > for longer than necessary). I've thought about that, and I don't see any problem. Since the "used part" of the array is read-only, I don't see any problem. If the value used as an initializer is referenced through any cell of the array, then the first cell - which still contain the same value - is also referenced as well. -- Alain |
From: Bardur A. <sp...@sc...> - 2005-03-06 05:49:37
|
Alain Frisch wrote: > Bardur Arantsson wrote: > >> I think there *might* be a problem with doing this. I don't remember >> the details right now, but I do remember being quite sure it was >> actually necessary to fill up using NULLs instead of copies. >> (Obviously it had something to do with the extra references causing >> objects to hang around for longer than necessary). > > > I've thought about that, and I don't see any problem. Since the "used > part" of the array is read-only, I don't see any problem. If the value > used as an initializer is referenced through any cell of the array, then > the first cell - which still contain the same value - is also referenced > as well. > Yup, you're certainly right about that. The only potential "problem" is in situations like with VList.map where you have references *after* the last_used: |---| \ |----| | . | |-- not x | .. | | . | / | .. | L-> | x | ---map---> | x' | <- L' | x | | ?? | | x | | ?? | |---| |----| Since the reference to L may be dropped later (and there are none before position L), you certainly don't want to set '??' to x; you want to set them to x'. So the "problem" is just that you have to be a bit more careful about initializers when copying the array. But since Array.create will actually "force" you to think about the initializer should be, it shouldn't be a problem in practise. (And besides, I only need to get the code right *once* :)) Thanks for the help, I'll remove all the NULL stuff some time today and make a new snapshot. -- Bardur Arantsson <ba...@im...> <ba...@sc...> It hovered above the ground, much in the way that bricks don't. Douglas Adams, 'Hitchiker's Guide to the Galaxy' |
From: Bardur A. <sp...@sc...> - 2005-03-06 07:30:28
|
Bardur Arantsson wrote: [--snip--] > > The test results are quite interesting. On my Athlon64 > 3500+, with 2GB of memory, a couple of test runs yield: > > $ ./examples/test1.opt > Benchmarks... > 10000000 x VList.(::)... 1.05192 > 10000000 x List.(::)... 2.28799 > 50000 x VList.nth... 0.000813007 > 50000 x List.nth... 14.4831 > 50000 x VList.length... 0.00608492 > 50000 x List.length... 32.4571 > 10000000 x cdr(VList)... 0.176178 > 10000000 x cdr(VList)... 0.116828 > $ ./examples/test1.opt > Benchmarks... > 10000000 x VList.(::)... 0.926367 > 10000000 x List.(::)... 2.01412 > 50000 x VList.nth... 0.00077486 > 50000 x List.nth... 12.8647 > 50000 x VList.length... 0.00628901 > 50000 x List.length... 32.2211 > 10000000 x cdr(VList)... 0.179661 > 10000000 x cdr(VList)... 0.131431 > [--snip--] I've updated the code to avoid NULLs (actually only required minimal changes... which was nice). It's available here: http://www.imada.sdu.dk/~bardur/ocaml-vlist-20050306.tar.bz2 Here's a benchmark with the old code, this time using floats: ./examples/test1.opt Benchmarks... 10000000 x VList.(::)... 3.1112 10000000 x List.(::)... 5.49784 50000 x VList.nth... 0.00185108 50000 x List.nth... 30.003 50000 x VList.length... 0.00599289 50000 x List.length... 63.9696 10000000 x cdr(VList)... 0.144912 10000000 x cdr(VList)... 0.242838 ... and here's the new code: ./examples/test1.opt Benchmarks... 10000000 x VList.(::)... 0.364121 10000000 x List.(::)... 5.17452 50000 x VList.nth... 0.00150108 50000 x List.nth... 29.8347 50000 x VList.length... 0.00717998 50000 x List.length... 64.5293 10000000 x VList.tl... 0.182895 10000000 x VList.tl... 0.246443 Quite a huge improvement for cons which fares *much* better against List in the case of huge lists of floats. I'm not sure if anyone actually uses huge lists of floats, but there you go. :) Other than that the performance is basically the same as before (both in the float case and the non-float case). Cheers, -- Bardur Arantsson <ba...@im...> <ba...@sc...> Just then, Neville caused a slight diversion by turning into a large canary. J.K. Rawling, 'Goblet of Fire' |