October 07, 2019
On Monday, 7 October 2019 at 19:38:50 UTC, mipri wrote:
> On Monday, 7 October 2019 at 19:16:31 UTC, IGotD- wrote:
>> On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:
>>>>
>>>> I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
>>> I'm sorry. Writing on my mobile phone. Maybe this is what you are looking for
>>> https://dlang.org/phobos/std_container_dlist.html
>>
>> I think what he is looking for are the general pop_front, push_front, pop_back and push_back that you would find in virtually any C++ STL container algorithms like list, vector or map.
>>
>> I think this is a good question as I don't really see any good example in the documentation of the dynamic arrays about this. This is very common use case for arrays. Is there any D equivalent?
>
> With the performance that you'd expect, I believe:
>
> #! /usr/bin/env rdmd
> [...]

I assume this is a little bit more complicated:
while popFront and popBack are ubiquitous in ranges in D, the push functions can't be unified in terms of memory management. For example, you cannot guarantee any performance, while using GC. This opposed to complexity, which is, of course, known.

Maybe, this is the reason, why such containers are omitted in Phobos (?)

But:
There is a priority queue, named binaryheap:
https://dlang.org/phobos/std_container_binaryheap.html

and there are hints, that for a stack you have to rely e.g., on an array or a list implementation
http://www.cplusplus.com/reference/stack/stack/
both exist in phobos:
https://dlang.org/phobos/std_container_array.html
https://dlang.org/phobos/std_container_dlist.html

This gives rise to user implementations like
https://code.dlang.org/packages/queue
https://code.dlang.org/packages/mergearray
etc.

Maybe, there will be more soon? ;)

October 07, 2019
On 10/07/2019 10:11 AM, Just Dave wrote:
> I need a stack and a queue

There is a DoubleEndedQueue example under "Indexing Operators" here:


http://ddili.org/ders/d.en/operator_overloading.html#ix_operator_overloading.opIndexOpAssign

It does not have the pop varieties but it should be trivial to add those because it internally uses two slices and the "head" of the whole container is the actual "end" of one of those slices. (The elementAt() member function takes care of reversed indexing for half of the elements.)

I stole the idea of that example from Chuck Allison after one of his DConf presentations.

Ali
October 08, 2019
On Monday, October 7, 2019 1:16:31 PM MDT IGotD- via Digitalmars-d-learn wrote:
> On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:
> >> I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
> >
> > I'm sorry. Writing on my mobile phone. Maybe this is what you are looking for https://dlang.org/phobos/std_container_dlist.html
>
> I think what he is looking for are the general pop_front, push_front, pop_back and push_back that you would find in virtually any C++ STL container algorithms like list, vector or map.
>
> I think this is a good question as I don't really see any good example in the documentation of the dynamic arrays about this. This is very common use case for arrays. Is there any D equivalent?

Pushing and popping like you'd do with a stack or queue can certainly be done with a dynamic array, but D's dynamic arrays don't work very well that way without wrapping them. Shrinking them is easy enough. You just slice the dynamic array to get another dynamic array which is a slice referring just to the elements that were sliced. e.g.

auto arr2 = arr1[5 .. $];
assert(arr2.length == arr1.length - 5);
assert(arr2 == arr1[5 .. $]);

If you just want to pop off the first element, you can even use popFront from std.range.primitives. e.g.

auto arr2 = arr1;
arr2.popFront();
assert(arr2 == arr1[1 .. $]);

Similarly, you could use popBack to pop off the last element. e.g.

auto arr2 = arr1;
arr2.popBack();
assert(arr2 == arr1[0 .. $ - 1]);

~= can be used to append to a dynamic array, but then we start getting into some issues.

When a dynamic array is appended to, the GC determines whether it has the capacity to put that element one past the end of that dynamic array within the block of memory that that dynamic array is a slice of. If the dynamic array is not a slice of GC-allocated memory for dynamic arrays, then the GC determines that it can't append in place, so it allocates a new block of memory, copies the elements to that new block of memory (including the appendend elements), and then mutates that dynamic array to point to the new block of memory. Similarly, if the dynamic array refers to a GC-allocated block of memory with no extra space on the end, the GC will allocate a new block of memory, copy the elements over, and mutate the dynamic array to point to the new block of memory. On the other hand, if the memory block was allocated by the GC for dynamic arrays, and it does have space beyond the end of that dynamic array, then it will just append in place and adjust the length member of the dynamic array accordingly. However, the real kicker for this particular use case is what happens when the dynamic array's last element is not the last element used within the memory block. e.g.

arr2 = arr1[0 .. $ - 1];
arr2 ~= 42;

or even

arr1 = arr1[0 .. $ - 1];
arr1 ~= 42;

Both of those examples will result in a new block of memory being allocated when the dynamic array is appended to. That's because the GC is written to avoid appending into another dynamic array which refers to the same block of memory. In order for a dynamic array to have capacity to expand into, no other dynamic array can ever have had any elements beyond the end of that dynamic array (the metadata keeps track of the farthest that any array has expanded into the block of memory). Even if there are currently no other dynamic arrays which refer to that element, it doesn't matter. All the GC cares about is whether any dynamic array has ever expanded that far into the memory block.

The result of this is that code like

stack.popBack();
stack ~= foo;
stack ~= bar;
stack.popBack();
stack ~= baz;

will end up allocating all over the place. Every time you append to the array after shrinking it, you're going to end up with the GC allocating a new block of memory instead of appending in place.

The solution to this problem is to use the function assumeSafeAppend (it's in object.d, so it's always available). e.g.

stack.popBack();
stack.assumeSafeAppend();
stack ~= foo;
stack ~= bar;
stack.popBack();
stack.assumeSafeAppend();
stack ~= baz;

This tells the GC to reset the metadata for the block of memory that that dynamic array is a slice of so that however far the last element of that dynamic array is is considered to be the last element curently used in the memory block. That way, when you append to it, it won't think that there are any other dynamic arrays using that memory, and it will expand the array in place.

The problem with this (and the reason that assumeSafeAppend is @system) is that if you ever use it when there are still other dynamic arrays in use which are slices of that same block of memory and which refer to elements beyond the end of the dynamic array that you call assumeSafeAppend on, you're going to get some subtle and nasty bugs. Because of that issue, it's not necessarily a great idea to put a tutorial for beginners somewhere about how to use a D dynamic array as a stack or queue. It can work quite well to use a dynamic array in the internal implementation of a stack or queue, but you probably don't want to do to it with a naked dynamic array.

The problem with queues isn't quite the same as with stacks, but it's also something that you need to be careful about. If you keep doing something like appending elements to the end and popping elements off of the front, that dynamic array is going to be an ever shifting slice of a memory block until it can't expand in place, and then you'd end up with a new memory block for that dynamic array being allocated. If the queue never gets very large, then you're just going to keep getting the underlying memory block for the dynamic array getting allocated over and over again without it growing, because when the array is reallocated, I'm pretty sure that the new size is based on the current size of the dynamic array, not the size of the underlying memory block.

Using std.algorithm's remove function instead of shrinking the slice at the front fixes that problem (it moves the elements forward within the dynamic array and then returns a dynamic array one element shorter), but then you need assumeSafeAppend, and it means that you're constantly moving the elements, which probably isn't good. There are of course several ways that this problem could be tackled to minimize the number of allocations while still avoiding constantly moving the elements around, but as with a stack, it's the sort of thing where you'd want to wrap the dynamic array in a struct or class to manage all of the logic required for pushing and popping elements instead of using a naked dynamic array.

- Jonathan M Davis




October 08, 2019
Thanks for the advice. I used a quick and dirty range solution as was suggested. It allowed me to move on as I really wasn't looking to fully implement a queue or stack. Just get something that semantically behaved as such. I'll return later and optimize it with the later suggestions if it's a major issue.
October 08, 2019
On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis wrote:
> The result of this is that code like
>
> stack.popBack();
> stack ~= foo;
> stack ~= bar;
> stack.popBack();
> stack ~= baz;
>
> will end up allocating all over the place. Every time you
> append to the array after shrinking it, you're going to end up
> with the GC allocating a new block of memory instead of
> appending in place.
>

Thanks as well! I thought the code I posted would only allocate when
the array ran out of capacity. And I see how, even if that's worked
around with assumeSafeAppend, it becomes a bad idea to define the
stack functions against `ref T[]` as this makes it too easy for other
code to slice the array and cause the bugs that assumeSafeAppend
allows.
October 08, 2019
On Tue, Oct 08, 2019 at 08:42:22PM +0000, mipri via Digitalmars-d-learn wrote:
> On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis wrote:
> > The result of this is that code like
> > 
> > stack.popBack();
> > stack ~= foo;
> > stack ~= bar;
> > stack.popBack();
> > stack ~= baz;
> > 
> > will end up allocating all over the place. Every time you append to the array after shrinking it, you're going to end up with the GC allocating a new block of memory instead of appending in place.
> > 
> 
> Thanks as well! I thought the code I posted would only allocate when the array ran out of capacity. And I see how, even if that's worked around with assumeSafeAppend, it becomes a bad idea to define the stack functions against `ref T[]` as this makes it too easy for other code to slice the array and cause the bugs that assumeSafeAppend allows.

IMO, the best way to implement a stack using built-in arrays is to wrap the array inside a struct that separately keeps track of the last element. Something like this:

	// Warning: untested code
	struct Stack(T) {
		private T[] impl;
		private size_t idx;
		...
		void push(T t) {
			if (impl.length <= idx)
				impl.length = ...; //expand by some amount
			impl[idx++] = t;
		}
		T pop() in(idx > 0) {
			// ... optional: reduce impl.length if idx /
			// .length ratio smalle than some threshold.

			return impl[idx--];
		}
	}


T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.
October 08, 2019
On Tuesday, October 8, 2019 2:42:22 PM MDT mipri via Digitalmars-d-learn wrote:
> On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis
>
> wrote:
> > The result of this is that code like
> >
> > stack.popBack();
> > stack ~= foo;
> > stack ~= bar;
> > stack.popBack();
> > stack ~= baz;
> >
> > will end up allocating all over the place. Every time you append to the array after shrinking it, you're going to end up with the GC allocating a new block of memory instead of appending in place.
>
> Thanks as well! I thought the code I posted would only allocate
> when
> the array ran out of capacity. And I see how, even if that's
> worked
> around with assumeSafeAppend, it becomes a bad idea to define the
> stack functions against `ref T[]` as this makes it too easy for
> other
> code to slice the array and cause the bugs that assumeSafeAppend
> allows.

Technically, it only does allocate when it runs out of capacity. However, if you do something like

arr = arr[0 .. $ - 1];

then arr.capacity will either be the length of the array or 0 (I don't remember which off the top of my head), because the capacity is calculated based on how much space is available after the end of the dynamic array. How much space is available at the end of the memory block is irrelevant unless the dynamic array includes the last element that any dynamic array has ever had within that memory block. If it's at the end, and the capacity is greater than the length of the array, then the array can expand in place (up to the difference between the length and the capacity). But if there is no extra room on the end, or if the current dynamic array is not at the end, then the capacity will reflect that. The same goes if the dynamic array is actually a slice of memory that wasn't allocated by the GC for dynamic arrays. IIRC, a dynamic array which is a slice of malloc-ed memory will always give a capacity of 0, but regardless of whether it's actually 0, it's never more than the length of the dynamic array, because there is no extra capacity to grow into, since the memory was not allocated by the GC for use by a dynamic array.

All of the various dynamic array functions work the same regardless of what kind of memory is backing the dynamic array. It's just that if the memory wasn't allocated by the GC for dynamic arrays, then when you call the dynamic array function or property, then the GC treats it the same as it would treat a dynamic array that referred to the end of the block of memory (and thus wouldn't have any extra capacity).

You should always be able to call capacity on a dynamic array and see whether appending to would then result in a reallocation or not.

Either way, because assumeSafeAppend resets the metadata so that the dynamic array it's given is considered to be the farthest dynamic array within the block of memory, after calling assumeSafeAppend, capacity will reflect that.

- Jonathan M Davis



1 2
Next ›   Last »