[concurrency-interest] ConcurrentSkipListMap visibility guarantees

Alexandre De Champeaux alexandre.dechampeaux at imc.com
Wed Jun 3 23:23:32 EDT 2020


Ah yes, I dumbed down the example too much…

Here it is again (But now with theSequence being updated inside add):

public class ConcurrentSkipListMapMissingRemove {
    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();
    private final static Comparator<DummyTimer> COMPARATOR = Comparator.comparing(DummyTimer::getSequence);
    private final static ConcurrentSkipListMap<DummyTimer, Long> TIMERS = new ConcurrentSkipListMap<>(COMPARATOR);

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; ++i) {
            CompletableFuture.runAsync(() -> {
                DummyTimer myDummyTimer = new DummyTimer();
                myDummyTimer.start();

                while (true) {
                    myDummyTimer.restart();
                }
            });
        }

        Thread.sleep(100_000_000);
    }

    private static class DummyTimer {
        private volatile long theSequence;

        void start() {
            add();
        }

        void restart() {
            remove();
            add();
        }

        private void add() {
            theSequence = SEQUENCE_CREATOR.getAndIncrement();
            TIMERS.put(this, theSequence);
        }

        private void remove() {
            if (TIMERS.remove(this) == null) {
                System.out.println("Ooops, failed to remove...");
            }
        }

        public long getSequence() {
            return theSequence;
        }
    }
}

From: Martin Buchholz <martinrb at google.com>
Date: Thursday, 4 June 2020 at 12:11 pm
To: Alexandre De Champeaux <alexandre.dechampeaux at imc.com>
Cc: "concurrency-interest at cs.oswego.edu" <concurrency-interest at cs.oswego.edu>
Subject: Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees

DummyTimer has no constructor, so they are all created with a sequence of zero, so initially they compare equal, so the map considers them equivalent, and so the initial add may fail.

On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <concurrency-interest at cs.oswego.edu<mailto:concurrency-interest at cs.oswego.edu>> wrote:
Hello concurrency interest,

I just came across some old code that concurrently does the following:

  1.  Remove Object o from ConcurrentSkipListMap
  2.  Mutate Object o
  3.  Add Object o back
Sometimes, the remove will fail.

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):


public class ConcurrentSkipListMapMissingRemove {
    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();
    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);
    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; ++i) {
            CompletableFuture.runAsync(() -> {
                DummyTimer myDummyTimer = new DummyTimer();
                myDummyTimer.start();

                while (true) {
                    myDummyTimer.restart();
                }
            });
        }

        Thread.sleep(100_000_000);
    }

    private static class DummyTimer {
        private volatile long theSequence;

        void start() {
            add();
        }

        void restart() {
            remove();
            theSequence = SEQUENCE_CREATOR.getAndIncrement();
            add();
        }

        private void add() {
            theTimers.put(this, theSequence);
        }

        private void remove() {
            if (theTimers.remove(this) == null) {
                System.out.println("Ooops, failed to remove...");
            }
        }

        public long getSequence() {
            return theSequence;
        }
    }
}

Thanks,

Alex
[Image removed by sender. IMC Logo]<https://www.imc.com/us/>

[Image removed by sender. F]<https://www.facebook.com/IMCTrading>


[Image removed by sender. t]<http://twitter.com/IMCTrading>


[Image removed by sender. I]<https://www.instagram.com/imctrading/>


[Image removed by sender. in]<https://www.linkedin.com/company/imc-financial-markets>


imc.com<https://www.imc.com/us/>


________________________________
The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
[IMC Logo]<https://www.imc.com/us/>

[F]<https://www.facebook.com/IMCTrading>


[t]<http://twitter.com/IMCTrading>


[I]<https://www.instagram.com/imctrading/>


[in]<https://www.linkedin.com/company/imc-financial-markets>


imc.com<https://www.imc.com/us/>


________________________________
The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20200604/cded809e/attachment-0001.htm>


More information about the Concurrency-interest mailing list