Slicing upward

[Jonathan M Davis]

On Saturday, September 14, 2019 5:34:35 AM MDT Brett via Digitalmars-d-learn 
wrote:
> I have an algorithm that is most efficiently implement by taking
> an array and slicing it upward, meaning removing the leading
> elements.
>
> Because the algorithm is complex(deterministic but chaotic) and
> deals with multiple arrays it is difficult to efficiently use
> slicing.
>
> Is there some easy way to take an array and slice it in a way
> that as the array grows any slices will "shift".
>
> Essentially it is sort of reversing how normal slices are
> represented
>
> [2,4,1,64]
> slice last 2, [1,64]
>
> append 3 to either one and both become
>
> [2,4,1,64,3]
> [1,64,3]
>
>
> In my case I will never have any slices in the middle.
>
> The easiest way, at the cost of size_t is to have an indexer that
> tells one how much to offset in to a standard array, basically
> skip the head.
>
> In the first it is 0 and the second it is 2.
>
> Since I already have the array though it is wasting space so I'm
> wondering if there is an easier way.
>
>
> Reversing the direction of the arrays does notwork because this
> then require massive copying of the array to prepend values.
>
> One can make an array type emulating this behavior but I'd rather
> have a simpler solution that is inline with slices, Else I'll
> just use the indexer method for simplicity.

No, that fundamentally goes against how D's dynamic arrays work. Their
representation is essentially

struct DynamicArray(T)
{
    size_t length;
    T* ptr;
}

They don't even have a concept of ownership. They merely point to a slice of
memory, and that memory isn't necessarily GC-allocated. In order to append
to a dynamic array, the GC looks at it to see if it's a slice of a block of
memory that the GC has allocated for dynamic arrays. If it is such a block
of memory _and_ the metadata associated with that block of memory indicates
that no other dynamic arrays have ever been expanded into the memory beyond
that dynamic array, then the GC will put the element being appended into the
next spot after the end of the dynamic array, adjust the metadata, and then
increment the length member of the dynamic array that it was passed. If, on
the other hand, that block of memory was not allocated by the GC, was
allocated by the GC for something other than dynamic arrays, or if the
metadata indicates that a dynamic array has already grown into the space
beyond the end of that dynamic array, then it will have to allocate a new
block of memory, copy the elements to that new block of memory, and then
adjust the dynamic array that it was passed so that its ptr and length
members then refer to the new block of memory.

In the case where no allocation occurs, in order for any other dynamic
arrays which happen to refer to that same block of memory and which happen
to have their last element at the same spot as the dynamic array being
appended to then also include that new element, the GC would have to do a
sweep of all of the memory in the program to see if any other dynamic arrays
exist which are slices of that same block of memory and adjust them
(basically, it would have to do what it does when it does a collection when
determining whether a block of memory can be freed). The same would be the
case if the dynamic array had to be reallocated, only then the ptr member
would have to be adjusted as well. Not only would such an approach be
horribly inefficient, but it wouldn't work with all of the use cases where
you want the other dynamic arrays which are slices of that same block of
memory to continue to refer to the exact same piece of that block of memory
that they've been referring to.

The entire design of D's dynamic arrays is built around the idea that they
don't own or manage any memory at all. They are merely slices of it. What
you're looking for implies an ownership relationship which simply does not
exist with D's dynamic arrays.

With D's dynamic arrays, there is no concept of there being a main one which
others are slices of. If two dynamic arrays are slices of the same block of
memory (whether they refer to exactly the same part of it or not), then they
are equal in standing. Neither of them owns the memory. They just point to
it.

To do what you're looking to do with dynamic arrays, you'd need another
layer of indirection - e.g. T[]* - where you then had a separate data type
for your "slices" of that dynamic array. e.g.

struct Slice(T)
{
    T[]* arr;
    size_t startIndex;
    size_t length;
}

would allow you to have a "slice" which always referred to the same elements
of a dynamic array even if the dynamic array were reallocated, or

struct Slice(T)
{
    T[]* arr;
    size_t startIndex;
}

would allow you to have the "slice" to expand when the dynamic array it
refers to expands.

In either case, if you're using a dynamic array to store the data, you'd
have to make sure that it was somewhere where it was going to stay valid as
long as the "slices" were around (e.g. a static variable or on the heap),
since if it's on the stack, and it goes out of scope, then your "slices"
won't refer to valid memory anymore even if the memory that the dynamic
array had referred to was still valid. It's the same problem you'd get if
you had a dynamic array which was a slice of a static array which was on the
stack, and the static array went out of scope.

- Jonathan M Davis