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.


 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.


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.


 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 
 
 


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.


 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



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.


 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


 
 
 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