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

use qrpa approach for ResizablePMCArray, add offset attr #1152

Closed
rurban opened this issue Nov 27, 2014 · 0 comments
Closed

use qrpa approach for ResizablePMCArray, add offset attr #1152

rurban opened this issue Nov 27, 2014 · 0 comments

Comments

@rurban
Copy link
Member

rurban commented Nov 27, 2014

i.e. use a moving array start index (=offset) and move this on shift, unshift or delete[0], instead of moving all array elements around.
just with consistent naming of the attributes. (ssize -> threshold, start -> offset, elems -> size, slots -> array)

qpra from nqp is much faster for the common shift and unshift ops. See http://irclog.perlgeek.de/perl6/2012-06-03/text
O(1) vs O(n), skipping a big memmove for 7 of 8 cases.

With this qrpa might be not needed anymore, esp. with its problems with sort within
threaded proxy pmcs.

Advantages over qrpa:

  • resize optimization with offsets, when there's enough room on the left
  • delete [0] with offsets just bumps the offset
  • faster push when there's enough room on the right
  • faster splice shrink when there's enough room on the left
  • does not fill slack elements right and left with PMCNULL, only when a out of bounds (oob) set leaves a hole.
  • sort is thread-safe
  • better over-allocation numbers. advance size by * 1.5 (via integer ops), which is close to the ideal golden ratio (better free list handling, see stack overflow). previously it was by * 2, as in perl5.

Disadvantages over old rpa's:

  • We cannot use inherited methods from FixedPMCArray (fpa) anymore, as fpa ignores the offset.
  • much more tricky logical cases to cover in the tests.

It's 15-25% faster in https://github.com/parrot/parrot-bench, 25% on slow machines, 15% on fast ones.

Further ideas:

We could add the following optimization thresholds:

  • on resize with move (ie push slow) reserve an offset > 0, maybe 3, for faster shifts.
  • on unshift slow (ie resize) reserve an offset, anticipating subsequent unshifts.
    we could check alignment inside unshift, which is better than in resize.
  • try initial size 4 instead of 8
@rurban rurban self-assigned this Nov 27, 2014
@rurban rurban added this to the 7.0.0 milestone Nov 27, 2014
rurban pushed a commit that referenced this issue Nov 27, 2014
offset is still const 0.
so the current PMCNULL error is in some incorrect refactoring.
rurban pushed a commit that referenced this issue Nov 27, 2014
using a max offset 8, as in nqp/qrpa. See GH #1152
Here offset is still const 0.
rurban pushed a commit that referenced this issue Nov 28, 2014
resizablepmcarray shift,unshift,resize,push,pop look now good.
just splice is missing.
rurban pushed a commit that referenced this issue Nov 28, 2014
Not offset optimized yet. It still fails.
GH #1152
rurban pushed a commit that referenced this issue Nov 30, 2014
resizablepmcarray shift,unshift,resize,push,pop look now good.
just splice is missing. GH #1152
rurban pushed a commit that referenced this issue Nov 30, 2014
Not offset optimized yet. And something still fails.
GH #1152
rurban pushed a commit that referenced this issue Dec 2, 2014
using a max offset 8, as in nqp/qrpa. See GH #1152
Here offset is still const 0.
rurban pushed a commit that referenced this issue Dec 2, 2014
resizablepmcarray shift,unshift,resize,push,pop look now good.
just splice is missing. GH #1152
rurban pushed a commit that referenced this issue Dec 2, 2014
Not offset optimized yet. And something still fails.
GH #1152
rurban pushed a commit that referenced this issue Dec 4, 2014
using a max offset 8, as in nqp/qrpa. See GH #1152
Here offset is still const 0.
rurban pushed a commit that referenced this issue Dec 4, 2014
resizablepmcarray shift,unshift,resize,push,pop look now good.
just splice is missing. GH #1152
rurban pushed a commit that referenced this issue Dec 4, 2014
Not offset optimized yet. And something still fails.
GH #1152
@rurban rurban closed this as completed in 6cbd12d Dec 5, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant