<div dir="ltr">The comparator is called with two keys in the map.  Even normally, the map has to deal with the possibility of a key being asynchronously removed while the comparator is running.  But it's really too much to expect that the map will be able to sanely handle the value of the key changing and being reinserted elsewhere in the map while the comparator is running.<div><br></div><div>Another way to look at it is that a key might be in use by a comparator for an arbitrarily long time after it has been removed, so the key object can never be mutated and reused.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 3, 2020 at 8:23 PM Alexandre De Champeaux <<a href="mailto:alexandre.dechampeaux@imc.com">alexandre.dechampeaux@imc.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">





<div lang="EN-AU">
<div class="gmail-m_1605684057624079682WordSection1">
<p class="MsoNormal"><span>Ah yes, I dumbed down the example too much…<u></u><u></u></span></p>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
<p class="MsoNormal"><span>Here it is again (But now with theSequence being updated inside add):<u></u><u></u></span></p>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">public class ConcurrentSkipListMapMissingRemove {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static Comparator<DummyTimer> COMPARATOR = Comparator.comparing(DummyTimer::getSequence);<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static ConcurrentSkipListMap<DummyTimer, Long> TIMERS = new ConcurrentSkipListMap<>(COMPARATOR);<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    public static void main(String[] args) throws InterruptedException {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        for (int i = 0; i < 10; ++i) {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            CompletableFuture.runAsync(() -> {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                DummyTimer myDummyTimer = new DummyTimer();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                myDummyTimer.start();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                while (true) {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                    myDummyTimer.restart();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            });<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        Thread.sleep(100_000_000);<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    private static class DummyTimer {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        private volatile long theSequence;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        void start() {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            add();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        void restart() {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            remove();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            add();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        private void add() {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            theSequence = SEQUENCE_CREATOR.getAndIncrement();<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            TIMERS.put(this, theSequence);<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        private void remove() {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            if (TIMERS.remove(this) == null) {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">                System.out.println("Ooops, failed to remove...");<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        public long getSequence() {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">            return theSequence;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">        }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">    }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Courier">}<u></u><u></u></span></p>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(181,196,223);padding:3pt 0cm 0cm">
<p class="MsoNormal"><b><span style="font-size:12pt;color:black">From: </span></b><span style="font-size:12pt;color:black">Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
<b>Date: </b>Thursday, 4 June 2020 at 12:11 pm<br>
<b>To: </b>Alexandre De Champeaux <<a href="mailto:alexandre.dechampeaux@imc.com" target="_blank">alexandre.dechampeaux@imc.com</a>><br>
<b>Cc: </b>"<a href="mailto:concurrency-interest@cs.oswego.edu" target="_blank">concurrency-interest@cs.oswego.edu</a>" <<a href="mailto:concurrency-interest@cs.oswego.edu" target="_blank">concurrency-interest@cs.oswego.edu</a>><br>
<b>Subject: </b>Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <<a href="mailto:concurrency-interest@cs.oswego.edu" target="_blank">concurrency-interest@cs.oswego.edu</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0cm 0cm 0cm 6pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal">Hello concurrency interest,<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">I just came across some old code that concurrently does the following:<u></u><u></u></p>
<ol start="1" type="1">
<li class="gmail-m_1605684057624079682gmail-m-2212015834539774438msolistparagraph">
Remove Object o from ConcurrentSkipListMap<u></u><u></u></li><li class="gmail-m_1605684057624079682gmail-m-2212015834539774438msolistparagraph">
Mutate Object o<u></u><u></u></li><li class="gmail-m_1605684057624079682gmail-m-2212015834539774438msolistparagraph">
Add Object o back<u></u><u></u></li></ol>
<p class="MsoNormal">Sometimes, the remove will fail.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Here is some code that reproduces (tried with Java 8u241 and 13.0.2):<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">public class ConcurrentSkipListMapMissingRemove {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    public static void main(String[] args) throws InterruptedException {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        for (int i = 0; i < 10; ++i) {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            CompletableFuture.runAsync(() -> {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                DummyTimer myDummyTimer = new DummyTimer();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                myDummyTimer.start();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                while (true) {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                    myDummyTimer.restart();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            });</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        Thread.sleep(100_000_000);</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    private static class DummyTimer {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        private volatile long theSequence;</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        void start() {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            add();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        void restart() {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            remove();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            theSequence = SEQUENCE_CREATOR.getAndIncrement();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            add();</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        private void add() {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            theTimers.put(this, theSequence);</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        private void remove() {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            if (theTimers.remove(this) == null) {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">                System.out.println("Ooops, failed to remove...");</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        public long getSequence() {</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">            return theSequence;</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">        }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">    }</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Courier">}</span><u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Thanks,<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Alex<u></u><u></u></p>
</div>
<p class="MsoNormal"><a href="https://www.imc.com/us/" target="_blank"><span style="color:windowtext;text-decoration:none"><span style="color:blue;border:1pt solid windowtext;padding:0cm"><img border="0" width="165" height="30" style="width: 1.7187in; height: 0.3125in;" id="gmail-m_1605684057624079682_x0000_i1030" alt="Image removed by sender. IMC Logo"></span></span></a><u></u><u></u></p>
<table border="0" cellspacing="0" cellpadding="0" width="450" style="width:337.5pt;border-collapse:collapse">
<tbody>
<tr>
<td width="32" style="width:24pt;padding:0cm">
<p style="line-height:12pt"><span style="font-family:Arial,sans-serif"><a href="https://www.facebook.com/IMCTrading" target="_blank"><span style="color:windowtext;text-decoration:none"><span style="color:blue;border:1pt solid windowtext;padding:0cm"><img border="0" width="32" height="32" style="width: 0.3333in; height: 0.3333in;" id="gmail-m_1605684057624079682_x0000_i1029" alt="Image removed by sender. F"></span></span></a><u></u><u></u></span></p>
</td>
<td width="32" style="width:24pt;padding:0cm 0cm 0cm 7.5pt">
<p style="line-height:12pt"><span style="font-family:Arial,sans-serif"><a href="http://twitter.com/IMCTrading" target="_blank"><span style="color:windowtext;text-decoration:none"><span style="color:blue;border:1pt solid windowtext;padding:0cm"><img border="0" width="32" height="32" style="width: 0.3333in; height: 0.3333in;" id="gmail-m_1605684057624079682_x0000_i1028" alt="Image removed by sender. t"></span></span></a><u></u><u></u></span></p>
</td>
<td width="32" style="width:24pt;padding:0cm 0cm 0cm 7.5pt">
<p style="line-height:12pt"><span style="font-family:Arial,sans-serif"><a href="https://www.instagram.com/imctrading/" target="_blank"><span style="color:windowtext;text-decoration:none"><span style="color:blue;border:1pt solid windowtext;padding:0cm"><img border="0" width="32" height="32" style="width: 0.3333in; height: 0.3333in;" id="gmail-m_1605684057624079682_x0000_i1027" alt="Image removed by sender. I"></span></span></a><u></u><u></u></span></p>
</td>
<td width="32" style="width:24pt;padding:0cm 0cm 0cm 7.5pt">
<p style="line-height:12pt"><span style="font-family:Arial,sans-serif"><a href="https://www.linkedin.com/company/imc-financial-markets" target="_blank"><span style="color:windowtext;text-decoration:none"><span style="color:blue;border:1pt solid windowtext;padding:0cm"><img border="0" width="32" height="32" style="width: 0.3333in; height: 0.3333in;" id="gmail-m_1605684057624079682_x0000_i1026" alt="Image removed by sender. in"></span></span></a><u></u><u></u></span></p>
</td>
<td style="padding:0cm 0cm 0cm 7.5pt">
<p style="line-height:12pt"><span style="font-size:11.5pt;font-family:Arial,sans-serif;color:rgb(0,130,186)"><a href="https://www.imc.com/us/" target="_blank"><strong><span style="font-family:Arial,sans-serif;color:rgb(0,130,186);text-decoration:none">imc.com</span></strong></a><u></u><u></u></span></p>
</td>
</tr>
</tbody>
</table>
<div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="color:white">
<hr size="0" width="100%" align="center">
</span></div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:Arial,sans-serif;color:gray">The information in this e-mail is intended only for the person or entity to which it is addressed.</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:Arial,sans-serif;color:gray"><br>
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.
</span><u></u><u></u></p>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
Concurrency-interest mailing list<br>
<a href="mailto:Concurrency-interest@cs.oswego.edu" target="_blank">Concurrency-interest@cs.oswego.edu</a><br>
<a href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><u></u><u></u></p>
</blockquote>
</div>
</div>


<a href="https://www.imc.com/us/" style="text-decoration:none" target="_blank"><img src="https://www.imc.com/media/1192/imc_logo_rgb_v_80b206.png" alt="IMC Logo" width="165" height="30" border="0"></a>
<table style="font-family:Arial;line-height:16px;border-collapse:collapse" width="450" cellspacing="0" cellpadding="0" border="0">
<tbody>
<tr>
<td style="padding-left:0px;padding-right:0px" width="32">
<p><a href="https://www.facebook.com/IMCTrading" style="text-decoration:none" target="_blank"><img src="https://www.imc.com/media/1188/social-02_v_206c6c.png" alt="F" width="32" height="32"></a></p>
</td>
<td style="padding-left:10px" width="32">
<p><a href="http://twitter.com/IMCTrading" style="text-decoration:none" target="_blank"><img src="https://www.imc.com/media/1189/social-03_v_517cd5.png" alt="t" width="32" height="32"></a></p>
</td>
<td style="padding-left:10px" width="32">
<p><a href="https://www.instagram.com/imctrading/" style="text-decoration:none" target="_blank"><img src="https://www.imc.com/media/1190/social-04_v_01e297.png" alt="I" width="32" height="32"></a></p>
</td>
<td style="padding-left:10px" width="32">
<p><a href="https://www.linkedin.com/company/imc-financial-markets" style="text-decoration:none" target="_blank"><img src="https://www.imc.com/media/1187/social-01_v_34b915.png" alt="in" width="32" height="32"></a></p>
</td>
<td style="padding-left:10px;vertical-align:middle">
<p style="font-size:15px;color:rgb(0,130,186)"><a href="https://www.imc.com/us/" style="color:rgb(0,130,186);text-decoration:none" target="_blank"><span style="text-decoration:none"><strong style="font-weight:bold;text-decoration:none">imc.com</strong></span></a></p>
</td>
</tr>
</tbody>
</table>
<div>
<hr>
</div>
<div><span style="color:gray;font-family:Arial;font-size:xx-small">The information in this e-mail is intended only for the person or entity to which it is addressed.</span></div>
<div><span style="color:gray;font-family:Arial;font-size:xx-small"><br>
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.
</span></div>
</div>

</blockquote></div>