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
↑ ↓←→ 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.
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
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
↑ ↓← → 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 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
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
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).
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
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 :)
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 :)
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
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
Home
| Search
| C & C++
| D
| DMDScript
| News Groups
| index
| prev
| next