adjustable arrays
in [Lisp]
|
Prev: Comparing Lisp to Python, what you consider more important: speed or macros.
Next: LispBox - truncated result?
From: Tamas K Papp on 29 Apr 2010 11:45 On Thu, 29 Apr 2010 15:13:30 +0000, Peter Keller wrote: > RG <rNOSPAMon(a)flownet.com> wrote: >> You want a displaced (and adjustable) array. >> >> ? (setf a1 (make-array 30)) >> #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) ? >> (dotimes (i 30) (setf (aref a1 i) i)) ... >> ? a1 >> #(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 >> 26 27 28 29) >> ? (setf a2 (make-array 10 :displaced-to a1 :displaced-index-offset 15 >> :adjustable t)) >> #(15 16 17 18 19 20 21 22 23 24) >> ? (adjust-array a1 '(15) :displaced-to a1 :displaced-index-offset 10) >> #(10 11 12 13 14 15 16 17 18 19 20 21 22 23 24) > > I see. > > If I knew how big the final sizes of the arrays were I could use this > method, but sadly I don't. I'll file away the method for another day. It > looks like under my circumstances, a new array into which I copy all of > my disparate pieces looks to be one of the only solutions. Sometimes I face a similar problem (collecting an number of items that are either unknown a prior, or I am lazy to calculate). I usually solve it the following way: create array with extra elements, keep using them until I run out, then create a new array with a buffer of extra elements, copy and continue. This way, you will copy occasionally, but not all the time. Example: (use-package '(:bind)) (defun prepend-elements (vector n &optional (extra 256)) (bind (((:values displaced-to index-offset) (array-displacement vector)) (new-length (+ n (length vector)))) (if (and displaced-to (<= n index-offset)) (make-array new-length :displaced-index-offset (- index-offset n) :displaced-to displaced-to) (let ((new-vector (make-array (+ extra new-length)))) (replace new-vector vector :start1 (+ extra n)) (make-array new-length :displaced-index-offset extra :displaced-to new-vector))))) (defparameter *a* #(1 2 3)) (setf *a* (prepend-elements *a* 7)) (array-displacement *a*) ; #(0 0 0 ...), 256 You can add bells and whistles, eg prepended element initialization, etc. Tamas
From: Peter Keller on 29 Apr 2010 12:12 Tamas K Papp <tkpapp(a)gmail.com> wrote: > Sometimes I face a similar problem (collecting an number of items that > are either unknown a prior, or I am lazy to calculate). I usually > solve it the following way: create array with extra elements, keep > using them until I run out, then create a new array with a buffer of > extra elements, copy and continue. This way, you will copy > occasionally, but not all the time. Example: Yeah, I thought of that. But it turns out the layering in my code base makes that difficult to acheive. My use case is I'm writing a master/worker style communication system which can handle 10,000 to 50,000 clients. Buffer management for me is a serious issue and I need to really conserve memory and not grind the allocator too much. The context is that when writing a data array to a client, the buffer management layer needs to wrap a header around the data before sending it. I thought about not doing the wrapping at all--just write the small header then the payload, but then that leads to alternating writes of a very small amount of data and then a large amount of data. That oscillation sucks from a network scheduling/bandwidth perspective. I need to write as many bytes as I can as often as I can. If it really looks like the write buffering will be problematic from a memory allocation point of view, I can make pools of buffers which are reusable for the assembling of the data. I don't want to do that initially since it is more code. I was just wondering if I had missed something in Lisp's array management which would allow me to grow an array at the head of the array. The answer is somewhat yes, but I'd have to preallocate the array and that means the application code would have to use a special abstraction of make-array. There are problems with that I'd rather avoid. I guess at this point, I'll just assemble the arrays naively and if the profiler tells me there is a problem there, I'll look into it deeper. Thank you. -pete
From: Giovanni Gigante on 29 Apr 2010 12:43 > My question is: This adjustment happens at the _end_ of the array, can I > expand the array at the beginning? Naive idea: what about building a list (you can cons to the beginning of that) and mapping it to an array only when you are done?
From: Mirko on 29 Apr 2010 12:43 On Apr 29, 12:12 pm, Peter Keller <psil...(a)merlin.cs.wisc.edu> wrote: > Tamas K Papp <tkp...(a)gmail.com> wrote: > > > Sometimes I face a similar problem (collecting an number of items that > > are either unknown a prior, or I am lazy to calculate). I usually > > solve it the following way: create array with extra elements, keep > > using them until I run out, then create a new array with a buffer of > > extra elements, copy and continue. This way, you will copy > > occasionally, but not all the time. Example: > > Yeah, I thought of that. But it turns out the layering in my code base makes > that difficult to acheive. > > My use case is I'm writing a master/worker style communication system > which can handle 10,000 to 50,000 clients. Buffer management for me is > a serious issue and I need to really conserve memory and not grind the > allocator too much. > > The context is that when writing a data array to a client, the buffer > management layer needs to wrap a header around the data before sending it.. > I thought about not doing the wrapping at all--just write the small header > then the payload, but then that leads to alternating writes of a very > small amount of data and then a large amount of data. That oscillation > sucks from a network scheduling/bandwidth perspective. I need to write > as many bytes as I can as often as I can. > > If it really looks like the write buffering will be problematic from > a memory allocation point of view, I can make pools of buffers which > are reusable for the assembling of the data. I don't want to do that > initially since it is more code. > > I was just wondering if I had missed something in Lisp's array management > which would allow me to grow an array at the head of the array. The > answer is somewhat yes, but I'd have to preallocate the array and that > means the application code would have to use a special abstraction of > make-array. There are problems with that I'd rather avoid. > > I guess at this point, I'll just assemble the arrays naively and if the > profiler tells me there is a problem there, I'll look into it deeper. > > Thank you. > > -pete Could it be that a different data structure would be more appropriate? What about a tree? (also, until recently, I had not realized how many different kinds of tree there are (2-3, 2-3-4, left leaning, etc). That would impact your access time, but in your case it may be manageable, or you could first store in tree, and then transfer into array. Mirko
From: RG on 29 Apr 2010 13:00
In article <4bd9afe9$0$9898$80265adb(a)spool.cs.wisc.edu>, Peter Keller <psilord(a)merlin.cs.wisc.edu> wrote: > Tamas K Papp <tkpapp(a)gmail.com> wrote: > > Sometimes I face a similar problem (collecting an number of items that > > are either unknown a prior, or I am lazy to calculate). I usually > > solve it the following way: create array with extra elements, keep > > using them until I run out, then create a new array with a buffer of > > extra elements, copy and continue. This way, you will copy > > occasionally, but not all the time. Example: > > Yeah, I thought of that. But it turns out the layering in my code base makes > that difficult to acheive. > > My use case is I'm writing a master/worker style communication system > which can handle 10,000 to 50,000 clients. Buffer management for me is > a serious issue and I need to really conserve memory and not grind the > allocator too much. > > The context is that when writing a data array to a client, the buffer > management layer needs to wrap a header around the data before sending it. > I thought about not doing the wrapping at all--just write the small header > then the payload, but then that leads to alternating writes of a very > small amount of data and then a large amount of data. That oscillation > sucks from a network scheduling/bandwidth perspective. I need to write > as many bytes as I can as often as I can. Seems to me then that what you want is not a growable array but rather smarter write buffering. > If it really looks like the write buffering will be problematic from > a memory allocation point of view, I can make pools of buffers which > are reusable for the assembling of the data. I don't want to do that > initially since it is more code. > > I was just wondering if I had missed something in Lisp's array management > which would allow me to grow an array at the head of the array. The > answer is somewhat yes, but I'd have to preallocate the array and that > means the application code would have to use a special abstraction of > make-array. There are problems with that I'd rather avoid. > > I guess at this point, I'll just assemble the arrays naively and if the > profiler tells me there is a problem there, I'll look into it deeper. That sounds like a fine plan. Premature optimization and all that. Memcpy is pretty frickin' fast, particularly when compared to network I/O. rg |