Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make Array to be workable as a queue, ie respect push+shift pattern. #5148

Closed
wants to merge 2 commits into from

Conversation

funny-falcon
Copy link
Contributor

To achieve it, pointer to allocation is preserved, and @buffer is moved
instead of moving elements on #shift.

This is draft for #5126

To achieve it, pointer to allocation is preserved, and @buffer is moved
instead of moving elements on `#shift`.

For crystal-lang#5126
If `@size == @capacity == 2**n-1`, then `Math.pw2ceil(@capacity + 1) == @capacity + 1`.
In this case, `push+shift` pattern leads to move on every `push`.
Avoid it by ensuring there is at least room for `@capacity/2` elements.
Also, quickly expand to capacity = 4 for small arrays.
@funny-falcon
Copy link
Contributor Author

Note, I don't propose accepting of this patch.
It has obvious negative effect of increasing Array's header.

@funny-falcon
Copy link
Contributor Author

funny-falcon commented Oct 20, 2017

And obviously, implementations of delete_at, insert and unshift should be improved to match Deque's performance.

@capacity += @buffer - @allocation
@allocation.move_from(@buffer, @size)
end
if @capacity != capacity
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think @capacity < capacity will be better. Because we can reuse what we already allocated.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 .

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Usually queue has sustained size, and then != will work adequately.

we already have @size for it.

resize_to_capacity is called not only from double_capacity. May be, there should be flag "increase", and then increase ? @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])

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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).

@jkthorne
Copy link
Contributor

@funny-falcon what is the status of this PR?

@funny-falcon
Copy link
Contributor Author

@wontruefree Status is same as it were: it works. But it is not clear: is it needed at all?

@jkthorne
Copy link
Contributor

@funny-falcon seems like from that other thread that this is something we should have.
@RX14 I hope you dont mind me bringing you into this PR. You seemed to be on the issue thread what are your thoughts on this PR?

@oprypin
Copy link
Member

oprypin commented May 29, 2018

There is no agreement on whether we want this, so stirring up the conversation on the PR makes little sense.

@jkthorne
Copy link
Contributor

This might be out of the scope of this PR but is there a conflict resolution process for the core team?

@oprypin
Copy link
Member

oprypin commented May 29, 2018

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.

@RX14
Copy link
Contributor

RX14 commented May 29, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants