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

Issue-228: Add unorderedSnapshot method to MpscArrayQueue and BaseMps… #229

Merged
merged 3 commits into from Apr 6, 2019

Conversation

srdo
Copy link
Contributor

@srdo srdo commented Jan 17, 2019

…cLinkedArrayQueue

Resolves #228

@coveralls
Copy link

coveralls commented Jan 17, 2019

Pull Request Test Coverage Report for Build 459

  • 0 of 0 changed or added relevant lines in 0 files are covered.
  • No unchanged relevant lines lost coverage.
  • Overall coverage remained the same at 47.61%

Totals Coverage Status
Change from base Build 457: 0.0%
Covered Lines: 1673
Relevant Lines: 3514

💛 - Coveralls

@nitsanw
Copy link
Contributor

nitsanw commented Jan 18, 2019

See comment on main ticket on API.

@@ -403,7 +417,6 @@ else if (casProducerIndex(pIndex, pIndex + 1))
{
final long offset = nextArrayOffset(mask);
final E[] nextBuffer = (E[]) lvElement(buffer, offset);
soElement(buffer, offset, null);
Copy link
Contributor

Choose a reason for hiding this comment

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

This will cause GC nepotism

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Thanks, wasn't aware of this issue. Will try to come up with a solution

Copy link
Contributor Author

Choose a reason for hiding this comment

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

I replaced this with a marker object that will cause the iterator to jump to the current consumerBuffer.

@@ -73,13 +77,22 @@ final boolean casProducerIndex(long expect, long newValue)
private volatile long consumerIndex;
protected long consumerMask;
protected E[] consumerBuffer;
private volatile E[] volatileConsumerBuffer;
Copy link
Contributor

@nitsanw nitsanw Jan 18, 2019

Choose a reason for hiding this comment

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

why do we need 2 consumer buffer refs?

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Should I make consumerBuffer volatile and add lp/lv/svConsumerBuffer methods instead?

Copy link
Contributor

Choose a reason for hiding this comment

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

why does it need to be volatile?

Copy link
Contributor Author

Choose a reason for hiding this comment

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

I wasn't aware that non-volatile reference writes/reads were always atomic. I guess it doesn't need to be volatile. Thanks.

public List<E> unorderedSnapshot() {
int length = capacity();
List<E> elements = new ArrayList<E>();
for (int i = 0; i < length; i++) {
Copy link
Contributor

Choose a reason for hiding this comment

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

You iterate through the whole array, very likely to be many thousands of elements, to find the elements you need

Copy link
Contributor Author

Choose a reason for hiding this comment

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

I'll try to make it less wasteful.

@nitsanw
Copy link
Contributor

nitsanw commented Jan 18, 2019

If we're going to add this access we will need some very clearly worded java doc on it's limitations and guarantees.

@srdo
Copy link
Contributor Author

srdo commented Jan 18, 2019

I've updated to provide iterators instead, and believe the GC nepotism issue should be avoided.

I made a minor change to the order of writes when replacing the consumer buffer. I would like to write the consumerBuffer field before the BUFFER_CONSUMED marker is inserted, to ensure the iterator doesn't see the BUFFER_CONSUMED flag along with the old consumerBuffer value, which would cause it to scan the same buffer again. Let me know if this isn't okay, and I'll be happy to revert.

I couldn't figure out a way to avoid scanning the entire buffer in the linked queues. I'd like to avoid skipping elements that are still queued, and as far as I can tell we will risk doing so if we follow the consumer index. If the iterator sees a mismatch between the consumerIndex and the current buffer, e.g. because the consumer just replaced consumerBuffer, it may start at the wrong position and end up skipping elements.

@nitsanw
Copy link
Contributor

nitsanw commented Apr 6, 2019

Sorry for taking long to re-review, this looks good :-)

@nitsanw nitsanw merged commit 58a08a1 into JCTools:master Apr 6, 2019
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

3 participants