Make Array to be workable as a queue, ie respect push+shift pattern. #5148
Conversation
To achieve it, pointer to allocation is preserved, and @buffer is moved instead of moving elements on `#shift`. For crystal-lang#5126
funny-falcon
force-pushed
the
array_queue
branch
from
ce42cdc to
b76ff8f
Compare
|
Note, I don't propose accepting of this patch. |
|
And obviously, implementations of |
| @capacity += @buffer - @allocation | ||
| @allocation.move_from(@buffer, @size) | ||
| end | ||
| if @capacity != capacity |
There was a problem hiding this comment.
I think @capacity < capacity will be better. Because we can reuse what we already allocated.
There was a problem hiding this comment.
Usually queue has sustained size, and then != will work adequately.
resize_to_capacity is called not only from double_capacity. May be, there should be flag "increase", and then increase ? @capacity < capacity : @capacity != capacity .
There was a problem hiding this comment.
Usually queue has sustained size, and then != will work adequately.
we already have @size for it.
resize_to_capacityis called not only fromdouble_capacity. May be, there should be flag "increase", and thenincrease ? @capacity < capacity : @capacity != capacity.
Yes, but they are requesting more memory than @capacity without adding @buffer - @allocation. Therefore, @capacity > capacity is possible. Here is example.
a = [0, 1, 2, 3, 4]
5.times { a.shift }
a.concat([0, 1, 2])There was a problem hiding this comment.
And what? It certainly should not forbid decrease of allocation size. Pleade, suggest something that will allow array to shrink its allocation. Ie differentiate situations where it should not shrink, and when it could shrink.
There was a problem hiding this comment.
Calling realloc to adjust size is slow, even though it is not too frequent. I would suggest
give a method to shrink size rather than automatic shrink.
There was a problem hiding this comment.
If we are going to "user should do it manually", then there is no sense in this PR at all. This PR is about adding "magic", and not "adding manual methods". User can use Deque, organaize priority queue, etc instead of using Array as a queue.
What about reallocing if @capacity < capacitu || @capacity > 8 && @capacity / 4 > capacity ?
And considering your example with 5.times { a.shift }; a.concat([1,2,3]) - it is pattern this PR aimed to fix. This PR is only about push + shift pattern. Improving for "any" pattern (for example, for "sorted insert" from #5153) should be next step.
It is possible to increase complexity of this PR and cover "sorted insert", "shift + concat", and all other combinations. But for this should decision from major contributors about future of this PR. It is not obvious if unification of Array and Deque is necessary at all (or at least, attractive).
|
@funny-falcon what is the status of this PR? |
|
@wontruefree Status is same as it were: it works. But it is not clear: is it needed at all? |
|
@funny-falcon seems like from that other thread that this is something we should have. |
|
There is no agreement on whether we want this, so stirring up the conversation on the PR makes little sense. |
|
This might be out of the scope of this PR but is there a conflict resolution process for the core team? |
|
In case it wasn't clear: perhaps you want to go to the issue that this references, and add your arguments for or against the idea of adding this. |
|
As long as the code works and it's not too complex I don't really mind merging this optimization. Complexity is really the only problem |
To achieve it, pointer to allocation is preserved, and @buffer is moved
instead of moving elements on
#shift.This is draft for #5126