Steven Schveighoffer wrote:
grauzone Wrote:
Steven Schveighoffer wrote:
The problem is that adding a capacity field only works if the object is a
reference type. A value type will make either choose to make copies of the
capacity field, resulting in the same stomping problem (and maybe worse), or
will zero out one of the copy's capacity field, resulting in an artificial
limitation for appending. The only true way to make this work right is to have
a capacity field shared among all the aliases to the same data, and the most
logical place for that is in the allocated block.
I see... Go makes slices value types (which references the array data),
but I'm not sure how or if they handle this situation.
Then, why use a cache to find the pointer to the capacity field inside
the array memory block? You could just store a pointer to the capacity
field in the slice.
Something like this, I guess:
struct slice {
void* ptr;
size_t length;
array_info* array;
}
[snip]
Would this work?
Yes, but the problem I see with it is you are passing around that array_info
pointer with the slice for *all* slices, not just ones you intend to use
appending on. There is plenty of code that uses arrays and slices without ever
doing appending, so that extra pointer is wasted space, and also increases the
cost of passing slices by value.
Suddenly having an additional field in the slice is the problem? Wasn't
semantics the problem (see your first reply to me above in this thread).
Is having an additional field in the slice really a problem?
You could just provide a "light" slice type. This wouldn't have the
additional helper field, and would consist only of a pointer and length
field. You could make it implicitly convertible to normal slices.
These light slices could be used by someone who needs the additional
performance so badly. Actually, they could simply be implemented as
library type.
I see no problem with adding an additional field to usual slices.
There's also some benefit: clearer semantics (if you make guaranteed
performance part of the semantics) and a much simpler runtime.
Your idea is essentially the idea behind my patch, except you can get the array
info without having an additional pointer. The cost of lookup for the block
info is mitigated by the cache, making lookups cost very little.
But the cache is volatile, and a cache entry could be easily flushed by
doing many array append operations. A single string processing function
could replace the entire cache with entries for string temporaries, and
cause nasty performance regressions in unrelated parts of the program
(e.g. in places where you really don't want each append operation to
reallocate the full array). The worst is, this behavior will be
relatively indeterministic. It's also hard to explain to "normal"
programmers.
Also, isn't it completely useless? If the programmer wants to append to
an array, he'll use an append struct just to be sure, and if he doesn't
want to append, inefficient array slice appending wouldn't be a problem.
You could avoid these issues just by adding a new field to the slice struct.
Needless to say, T[new] would be the correct solution here. It also has
cleaner semantics. Yes, I heard it sucked and it was considered a
failure by Walter/Andrei, but we still don't know why.
The patch is a compromise between performance for appending and performance for
everything else. I think there will still be a need in specialized code for a
fatter array type that allows appending without complicated GC lookups, but the
patch provides safe appending for a reasonable performance hit without
affecting other aspects of array usage. As with all compromises, there are
always different ways of doing things, so time will tell if this patch is the
best method.
-Steve
