<div dir="ltr"><div class="gmail_quote"><div>Hi Compl,</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p>>+ <span style="color:rgb(200,195,188);font-family:"PT Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Oxygen-Sans,Cantarell,"Helvetica Neue",sans-serif;font-size:17px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:0.024px;text-align:left;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(25,27,28);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">This package provides a
        proof-of-concept implementation of a skip list in STM</span></p>
    <p>This has to mean something but I can't figure out yet.<br>
    </p>
    <p>Dear Peter Robinson, I hope you can see this message and get in
      the loop of discussion. </p></div></blockquote></div></div></blockquote><div><br></div><div> The reason for adding this sentence was that tskiplist hasn't been optimized for production use. Later on, I wrote an implementation of a concurrent skip list with atomic operations that performs significantly better, but it's operations work in the IO monad. </div><br>I'm surprised to hear that you're getting poor performance even when using the stm-container package, which I believe was meant to be used in production. A while ago, I ran some benchmarks comparing concurrent dictionary data structures (such as stm-container) under various workloads. While STMContainers.Map wasn't as fast as the concurrent-hashtable package, the results indicate that the performance doesn't degrade too much under larger workloads.<br><br>You can find these benchmark results here (10^6 randomly generated insertion/deletion/lookup requests distributed among 32 threads): <br><a href="https://lowerbound.io/blog/bench2-32.html">https://lowerbound.io/blog/bench2-32.html</a>   <br>And some explanations about the benchmarks are here:  <br><a href="https://lowerbound.io/blog/2019-10-24_concurrent_hash_table_performance.html">https://lowerbound.io/blog/2019-10-24_concurrent_hash_table_performance.html</a><br>  <br>One issue that I came across when implementing the tskiplist package was this: If a thread wants to insert some item into the skip list, it needs to search for the entry point by performing readTVar operations starting at the list head. So, on average, a thread will read O(log n) TVars (assuming a skip list of n items) and, if any of these O(log n) TVars are modified by a simultaneously running thread, the STM runtime will observe a (false) conflict and rerun the transaction. It's not clear to me how to resolve this issue without access to something like unreadTVar (see [1]).  <br><br>Best,<br>Peter<br><br>[1] UnreadTVar: Extending Haskell Software Transactional Memory for Performance (2007)  by Nehir Sonmez , Cristian Perfumo , Srdjan Stipic , Adrian Cristal , Osman S. Unsal , Mateo Valero.<br></div><div class="gmail_quote"><br></div></div>