www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Feature Request: Linked Arrays

reply downs <default_357-line yahoo.de> writes:
Since one of D's weaknesses is bad speed when appending to dynamic arrays, I've
been thinking about a way to fix this.

Linked arrays are a hybrid between flat arrays and linked list: a single linked
list of array chunks.

Basically, a linked array (syntax: T[>], new T[50>]) looks like this:

struct LinkedArray {
  void* start;
  size_t my_length;
  size_t length();
  LinkedArray* nextBlock, lastBlock;
}

When appending to a LinkedArray, it is first checked if the current block can
be grown to accomodate the new member(s) *without* reallocating.

If it can't, instead of reallocating and copying, a new LinkedArray is tacked
on the end.

Because of this, there is never redundancy as with current arrays, and the load
on the GC can be vastly reduced.

Appending is also much closer to linear than with current arrays. This makes
Linked Arrays highly suitable for queues and buffers.

On the other hand, they're completely incompatible with C libraries, don't
expose a .ptr property (not flat), and because of the complexities of their
layout, all slices have to be constant (value, not reference).

But these disadvantages are, imho, more than made up by the benefits they'd
offer as an alternative to current arrays.

Also, they don't need new keywords :)

Whaddya think?

 --downs
May 01 2008
next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
downs wrote:
 Since one of D's weaknesses is bad speed when appending to dynamic arrays,
I've been thinking about a way to fix this.
 
 Linked arrays are a hybrid between flat arrays and linked list: a single
linked list of array chunks.
 
 Basically, a linked array (syntax: T[>], new T[50>]) looks like this:
 
 struct LinkedArray {
   void* start;
   size_t my_length;
   size_t length();
   LinkedArray* nextBlock, lastBlock;
 }
 
 When appending to a LinkedArray, it is first checked if the current block can
be grown to accomodate the new member(s) *without* reallocating.
 
 If it can't, instead of reallocating and copying, a new LinkedArray is tacked
on the end.
 
 Because of this, there is never redundancy as with current arrays, and the
load on the GC can be vastly reduced.
 
 Appending is also much closer to linear than with current arrays. This makes
Linked Arrays highly suitable for queues and buffers.
 
 On the other hand, they're completely incompatible with C libraries, don't
expose a .ptr property (not flat), and because of the complexities of their
layout, all slices have to be constant (value, not reference).
 
 But these disadvantages are, imho, more than made up by the benefits they'd
offer as an alternative to current arrays.
 
 Also, they don't need new keywords :)
 
 Whaddya think?
 
  --downs

I'd rather ask the GC to expose a canExpand() method and have it implemented in the library.
May 01 2008
next sibling parent reply janderson <askme me.com> writes:
Robert Fraser wrote:
 downs wrote:
 Since one of D's weaknesses is bad speed when appending to dynamic 
 arrays, I've been thinking about a way to fix this.

 Linked arrays are a hybrid between flat arrays and linked list: a 
 single linked list of array chunks.

 Basically, a linked array (syntax: T[>], new T[50>]) looks like this:

 struct LinkedArray {
   void* start;
   size_t my_length;
   size_t length();
   LinkedArray* nextBlock, lastBlock;
 }

 When appending to a LinkedArray, it is first checked if the current 
 block can be grown to accomodate the new member(s) *without* 
 reallocating.

 If it can't, instead of reallocating and copying, a new LinkedArray is 
 tacked on the end.

 Because of this, there is never redundancy as with current arrays, and 
 the load on the GC can be vastly reduced.

 Appending is also much closer to linear than with current arrays. This 
 makes Linked Arrays highly suitable for queues and buffers.

 On the other hand, they're completely incompatible with C libraries, 
 don't expose a .ptr property (not flat), and because of the 
 complexities of their layout, all slices have to be constant (value, 
 not reference).

 But these disadvantages are, imho, more than made up by the benefits 
 they'd offer as an alternative to current arrays.

 Also, they don't need new keywords :)

 Whaddya think?

  --downs

I'd rather ask the GC to expose a canExpand() method and have it implemented in the library.

I agree. BTW, to state the obvious: "Linked arrays" have several dis-advantages when compared to arrays. Namely after a while of lots of insertions deletions they become very fragmented and performance slows down. The main thing you have to watch out for is traversal. Often I've seen code slow down because people write a data structure to speed up insertion, not realizing that most of the time was spent in traversal. By using links the work of the pre-fetcher, code optimizer and cache is increased. Granted, lots of long small arrays are better then a link-list however it has nothing on single array traversal. So really to figure out how your data will be used. How many times will a node be visited verse how many times you'll insert something. As a game programmer, typically array nodes have the potential to be visited several times (maybe every frame) however things can only be inserted once (and normally at the end of the array). One think what would help, is if you could get the next free aligned block in memory from the previous block. That way the array would be slightly more cache friendly. I'm not saying this sort of data struct doesn't have it's uses, sometimes its useful for minimizing Memory Manager fragmentation. In fact if you have a huge array, sometimes the only way to get around fragmentation is to spit it up. -Joel
May 01 2008
parent reply downs <default_357-line yahoo.de> writes:
janderson wrote:
 Robert Fraser wrote:
 I'd rather ask the GC to expose a canExpand() method and have it
 implemented in the library.

I agree.

So do I, actually. That would be best.
 
 BTW, to state the obvious:
 
 "Linked arrays" have several dis-advantages when compared to arrays.
 Namely after a while of lots of insertions deletions they become very
 fragmented and performance slows down.

I don't see how that could happen, if you're only appending at the end.
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

It depends on the size of the elements. If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably. I don't have the benchs to demonstrate that though. Sorry.
 One think what would help, is if you could get the next free aligned
 block in memory from the previous block.  That way the array would be
 slightly more cache friendly.
 

I don't understand.
 I'm not saying this sort of data struct doesn't have it's uses,
 sometimes its useful for minimizing Memory Manager fragmentation.  In
 fact if you have a huge array, sometimes the only way to get around
 fragmentation is to spit it up.

That's the idea :) Currently, appending to an array is almost embarassingly slow. This forces the use of preallocating, which is unintuitive. Imnsho :)
 
 -Joel

--downs
May 02 2008
next sibling parent Christopher Wright <dhasenan gmail.com> writes:
downs wrote:
 janderson wrote:
 Robert Fraser wrote:
 I'd rather ask the GC to expose a canExpand() method and have it
 implemented in the library.


So do I, actually. That would be best.
 BTW, to state the obvious:

 "Linked arrays" have several dis-advantages when compared to arrays.
 Namely after a while of lots of insertions deletions they become very
 fragmented and performance slows down.

I don't see how that could happen, if you're only appending at the end.

If you're only appending at the end, why use a linked array? Simply so your array does not need to be contiguous?
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

It depends on the size of the elements. If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably. I don't have the benchs to demonstrate that though. Sorry.

Data locality is a strong advantage, too. It depends, I think, on how often you are planning on appending to the array. I think most people usually use small arrays most of the time, but I don't have data for this.
 One think what would help, is if you could get the next free aligned
 block in memory from the previous block.  That way the array would be
 slightly more cache friendly.

I don't understand.

When you access memory, the OS pulls in at least one page to cache. Often it'll pull in a bit more, since you're likely to access memory with nearby addresses. So if you plan your data layout around this, you get better performance.
 I'm not saying this sort of data struct doesn't have it's uses,
 sometimes its useful for minimizing Memory Manager fragmentation.  In
 fact if you have a huge array, sometimes the only way to get around
 fragmentation is to spit it up.

That's the idea :) Currently, appending to an array is almost embarassingly slow. This forces the use of preallocating, which is unintuitive. Imnsho :)

The method is, I think, but not the idea.
May 02 2008
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"downs" wrote
 janderson wrote:
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

It depends on the size of the elements. If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably.

If each array chunk is the same size, you could store the array in an array of arrays. Then lookup time becomes O(1), and appending data is not going to cause a copy of the other array chunks that you already have allocated. If you add a huge piece that is bigger than one chunk, just allocate that piece, then slice the piece up into chunks. It could actually be an array of pointers, assuming all your chunks are the same size. I'd prefer that to a linked list of arrays, where traversal is O(n) (with a small constant) -Steve
May 02 2008
next sibling parent janderson <askme me.com> writes:
Steven Schveighoffer wrote:
 "downs" wrote
 janderson wrote:
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably.

If each array chunk is the same size, you could store the array in an array of arrays. Then lookup time becomes O(1), and appending data is not going to cause a copy of the other array chunks that you already have allocated. If you add a huge piece that is bigger than one chunk, just allocate that piece, then slice the piece up into chunks. It could actually be an array of pointers, assuming all your chunks are the same size. I'd prefer that to a linked list of arrays, where traversal is O(n) (with a small constant) -Steve

Yes this is often better, although it depends on what you are doing. -Joel
May 02 2008
prev sibling parent reply downs <default_357-line yahoo.de> writes:
Steven Schveighoffer wrote:
 If each array chunk is the same size, you could store the array in an array 
 of arrays.  Then lookup time becomes O(1), and appending data is not going 
 to cause a copy of the other array chunks that you already have allocated.
 

Yeah but that just reduces the appending problem, not removes it. Admittedly, this might be sufficient in many cases.
 If you add a huge piece that is bigger than one chunk, just allocate that 
 piece, then slice the piece up into chunks.
 
 It could actually be an array of pointers, assuming all your chunks are the 
 same size.
 
 I'd prefer that to a linked list of arrays, where traversal is O(n) (with a 
 small constant)

Um, excuse me but isn't traversal always O(n)? Perhaps you meant lookup - keep in mind that my original proposal was not intended for situations where random lookup is important (queues, buffers and stacks).
 
 -Steve 
 
 

May 03 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"downs" wrote
 Steven Schveighoffer wrote:
 If each array chunk is the same size, you could store the array in an 
 array
 of arrays.  Then lookup time becomes O(1), and appending data is not 
 going
 to cause a copy of the other array chunks that you already have 
 allocated.

Yeah but that just reduces the appending problem, not removes it. Admittedly, this might be sufficient in many cases.

It basically reduces the copy of all the data to just the copy of the array headers. If each array chunk is a page, 4096 bytes, then a page of array headers (on a 32-bit arch) is 4096 / 8 = 512 chunks * 4096 bytes = 2MB before you have to reallocate the array header array. And then each time you reallocate, you get another 2MB. If you size your array chunk size appropriately, or pre-allocate the pages for your array of arrays, then you get even better performance. Change the array headers to pointers, and you get double the performance. I'd think it would be very comparable to a link-list of arrays.
 If you add a huge piece that is bigger than one chunk, just allocate that
 piece, then slice the piece up into chunks.

 It could actually be an array of pointers, assuming all your chunks are 
 the
 same size.

 I'd prefer that to a linked list of arrays, where traversal is O(n) (with 
 a
 small constant)

Um, excuse me but isn't traversal always O(n)? Perhaps you meant lookup - keep in mind that my original proposal was not intended for situations where random lookup is important (queues, buffers and stacks).

When someone mentioned that traversal would be a problem, I assumed that was when you want to do random lookup. Random lookup is O(n) with a LL of arrays, with a very small constant (because you skip n elements at a time per link). The point of my suggestion was to reduce the lookup time. You could have queue/buffer behavior, but all you need to reallocate is the headers. I admit, the link-list version might be better memory-wise than my solution in that regard. -Steve
May 04 2008
prev sibling parent reply janderson <askme me.com> writes:
downs wrote:
 janderson wrote:
 Robert Fraser wrote:
 I'd rather ask the GC to expose a canExpand() method and have it
 implemented in the library.


So do I, actually. That would be best.
 BTW, to state the obvious:

 "Linked arrays" have several dis-advantages when compared to arrays.
 Namely after a while of lots of insertions deletions they become very
 fragmented and performance slows down.

I don't see how that could happen, if you're only appending at the end.
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

It depends on the size of the elements. If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably. I don't have the benchs to demonstrate that though. Sorry.
 One think what would help, is if you could get the next free aligned
 block in memory from the previous block.  That way the array would be
 slightly more cache friendly.

I don't understand.
 I'm not saying this sort of data struct doesn't have it's uses,
 sometimes its useful for minimizing Memory Manager fragmentation.  In
 fact if you have a huge array, sometimes the only way to get around
 fragmentation is to spit it up.

That's the idea :) Currently, appending to an array is almost embarassingly slow. This forces the use of preallocating, which is unintuitive. Imnsho :)
 -Joel

--downs

This may help: http://video.google.com/videosearch?hl=en&safe=off&pwst=1&resnum=0&q=herb%20sutter&um=1&ie=UTF-8&sa=N&tab=wv Note that smallest cache lines could be as small as 64bit. -Joel
May 02 2008
parent janderson <askme me.com> writes:
janderson wrote:
 downs wrote:
 janderson wrote:
 Robert Fraser wrote:
 I'd rather ask the GC to expose a canExpand() method and have it
 implemented in the library.


So do I, actually. That would be best.
 BTW, to state the obvious:

 "Linked arrays" have several dis-advantages when compared to arrays.
 Namely after a while of lots of insertions deletions they become very
 fragmented and performance slows down.

I don't see how that could happen, if you're only appending at the end.
 The main thing you have to
 watch out for is traversal. Often I've seen code slow down because
 people write a data structure to speed up insertion, not realizing that
 most of the time was spent in traversal.  By using links the work of the
 pre-fetcher, code optimizer and cache is increased.

It depends on the size of the elements. If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably. I don't have the benchs to demonstrate that though. Sorry.
 One think what would help, is if you could get the next free aligned
 block in memory from the previous block.  That way the array would be
 slightly more cache friendly.

I don't understand.
 I'm not saying this sort of data struct doesn't have it's uses,
 sometimes its useful for minimizing Memory Manager fragmentation.  In
 fact if you have a huge array, sometimes the only way to get around
 fragmentation is to spit it up.

That's the idea :) Currently, appending to an array is almost embarassingly slow. This forces the use of preallocating, which is unintuitive. Imnsho :)
 -Joel

--downs

This may help: http://video.google.com/videosearch?hl=en&safe=off&pwst=1&resnum=0&q=herb%20sutter&um=1& e=UTF-8&sa=N&tab=wv Note that smallest cache lines could be as small as 64bit. -Joel

Also you should be aware of this trick: array.length = 100; array.length = 0; Will preallocate memory for you. -Joel
May 02 2008
prev sibling parent Sean Kelly <sean invisibleduck.org> writes:
Robert Fraser wrote:
 
 I'd rather ask the GC to expose a canExpand() method and have it 
 implemented in the library.

Easy enough, use GC.sizeOf in Tango or std.gc.capacity in Phobos. Sean
May 02 2008
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
downs Wrote:
 Whaddya think?

In my libs I'll add a Deque class with that structure, that module code is currently in debugging phase. So I think they can be useful. Bye, bearophile
May 02 2008
prev sibling parent BLS <nanali nospam-wanadoo.fr> writes:
downs schrieb:
 Since one of D's weaknesses is bad speed when appending to dynamic arrays,
I've been thinking about a way to fix this.
 
 Linked arrays are a hybrid between flat arrays and linked list: a single
linked list of array chunks.

So it would be nice to have a datastructure that is a mixture of a <Vector> and a <LinkedList>. A list-implementation that automatically handles allocation of needed space quite efficiently, provides fast index-based access *and* fast insertions and removals. List.d tries to behave like a <Vector> and thus like a dynamic array if possible: if T.sizeof <= (void*).sizeof behave like vector else behave circular linked list // to solve the head tail problem I think it is worth to have a look at Uwe Salomons list implementation. dsource indigo/tools/list.d based on : http://doc.trolltech.com/4.0/qlist.html Bjoern
May 07 2008