<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Aug 9, 2017 at 5:54 AM, Daniel Vollmer via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br>
> On 9. Aug 2017, at 06:51, Taylor Swift via swift-users <<a href="mailto:swift-users@swift.org">swift-users@swift.org</a>> wrote:<br>
><br>
> It’s possible to implement a classic red-black tree in Swift that performs better than a sorted Array, down to about n = 1,500 items, not n = 100,000 items as it claims. (Actually, heap allocators these days are good enough that performance is on par with Array all the way down to n = 1.)<br>
<br>
</span>I’m not sure how that can be because you lose locality (but that probably depends on what operations “perform” includes). And IMO, heap allocations remain (and will remain) a bottleneck for small allocations.<br>
<br>
Daniel.<br>
<div class="HOEnZb"><div class="h5">______________________________<wbr>_________________<br><br></div></div></blockquote><div><br></div><div>If the number of nodes is small, Swift’s heap allocator will actually place then contiguously in memory, just like an Array, as long as you don’t wait too long between calls to insert(_:). You can also write your own simple memory allocator in Swift that’s backed by an <span style="font-family:monospace,monospace">Array</span> which guarantees the nodes will live near each other in memory. But that’s getting off topic lol<br></div></div><br></div></div>