Persistent arrays
in [Lisp]
|
From: Slobodan Blazeski on 27 Mar 2010 13:03 I'm working with arrays that are one dimensional,adjustable, hold only one type of element and could get quite long(*). I need a way to save them in the file system after doing some work with them (like inserting , deleting and/or changing elements). Quick test of cl-store for storing an array of 10 000 000 fixnums takes 31.8 MB and the > 3 sec to run. So what would you suggest as a pure lisp storing strategy? thanks Slobodan (*) Sample array: (make-array 10000000 :element-type 'fixnum :initial-element 19 :fill- pointer t :adjustable t)
From: Tamas K Papp on 27 Mar 2010 13:43 On Sat, 27 Mar 2010 10:03:34 -0700, Slobodan Blazeski wrote: > I'm working with arrays that are one dimensional,adjustable, hold only > one type of element and could get quite long(*). I need a way to save > them in the file system after doing some work with them (like inserting > , deleting and/or changing elements). Quick test of cl-store for storing > an array of 10 000 000 fixnums takes 31.8 MB and the > 3 sec to run. > So what would you suggest as a pure lisp storing strategy? > (*) Sample array: > (make-array 10000000 :element-type 'fixnum :initial-element 19 :fill- > pointer t :adjustable t) Have you tried writing it our in binary form? Ie take the fixnums, slice them up as bytes, open a byte stream, etc. This is the fastest portable solution I can think of. On SBCL, you might want to try http://github.com/nikodemus/sb-vector-io Tamas
From: allchemist on 27 Mar 2010 13:50 The naive way is to print elements of the vector one-by-one. but it is surely unresonable. Then you can write a pack of elements at one time, you may also try something like #'write-sequence. But if the size of output file is 31.8 Mb, the time 3 seconds may be the limit of your hard disk writing speed. If not, you may also try to dump the lisp image containing the data. It seems to be the most simple way, but with some overhead.
From: Slobodan Blazeski on 27 Mar 2010 14:03 On Mar 27, 6:43 pm, Tamas K Papp <tkp...(a)gmail.com> wrote: > On Sat, 27 Mar 2010 10:03:34 -0700, Slobodan Blazeski wrote: > > I'm working with arrays that are one dimensional,adjustable, hold only > > one type of element and could get quite long(*). I need a way to save > > them in the file system after doing some work with them (like inserting > > , deleting and/or changing elements). Quick test of cl-store for storing > > an array of 10 000 000 fixnums takes 31.8 MB and the > 3 sec to run. > > So what would you suggest as a pure lisp storing strategy? > > (*) Sample array: > > (make-array 10000000 :element-type 'fixnum :initial-element 19 :fill- > > pointer t :adjustable t) > > Have you tried writing it our in binary form? Ie take the fixnums, > slice them up as bytes, open a byte stream, etc. This is the fastest > portable solution I can think of. > > On SBCL, you might want to try > > http://github.com/nikodemus/sb-vector-io > > Tamas Thanks for the link but my problem is not the size of the stored files (though its certainly nice to save space) but rather I want to achieve some sort of the safety that databases provide. Something like cl- prevalence and AllegroCache do for classes(*). Maybe transaction log might help, or splicing the arrays in smaller manageable chunks, or using deltas(*). Basically I don't want to touch data after it has been written. Slobodan (*) http://www.ericsink.com/entries/time_space_tradeoffs.html
From: Tamas K Papp on 27 Mar 2010 14:48
On Sat, 27 Mar 2010 11:03:05 -0700, Slobodan Blazeski wrote: > On Mar 27, 6:43 pm, Tamas K Papp <tkp...(a)gmail.com> wrote: >> On Sat, 27 Mar 2010 10:03:34 -0700, Slobodan Blazeski wrote: >> > I'm working with arrays that are one dimensional,adjustable, hold >> > only one type of element and could get quite long(*). I need a way to >> > save them in the file system after doing some work with them (like >> > inserting , deleting and/or changing elements). Quick test of >> > cl-store for storing an array of 10 000 000 fixnums takes 31.8 MB >> > and the > 3 sec to run. So what would you suggest as a pure lisp >> > storing strategy? (*) Sample array: >> > (make-array 10000000 :element-type 'fixnum :initial-element 19 >> > :fill- >> > pointer t :adjustable t) >> >> Have you tried writing it our in binary form? Ie take the fixnums, >> slice them up as bytes, open a byte stream, etc. This is the fastest >> portable solution I can think of. >> >> On SBCL, you might want to try >> >> http://github.com/nikodemus/sb-vector-io >> >> Tamas > > Thanks for the link but my problem is not the size of the stored files > (though its certainly nice to save space) but rather I want to achieve > some sort of the safety that databases provide. Something like cl- > prevalence and AllegroCache do for classes(*). Maybe transaction log > might help, or splicing the arrays in smaller manageable chunks, or > using deltas(*). Basically I don't want to touch data after it has been > written. > > Slobodan > (*) http://www.ericsink.com/entries/time_space_tradeoffs.html I would guess that in this case, the hard disk is the actual bottleneck, so saving space would save you time. There is no time-space trade-off, quite the opposite. Also, I don't understand why you need a transaction log if you don't change the data. If you change the data occasionally, I would just use git or similar. A not-so-suboptimal solution to your problem would be writing out a readable representation (eg a list or a vector), then reading it in using READ and creating an array with that as initial contents. Probably not as fast as byte streams, but still quite good and robust. Also, if you use linebreaks instead of spaces, git will keep track of the changes with minimal overhead. Best, Tamas |