<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Sounds fair. I would be trying for a refactoring approach, in
that the API and outward behaviour is identical to before (i.e. a
black box), but the inner workings are better. I noticed that one
potential source of improvement is changing the Quicksort
algorithm, used in most of the sorting, for Introsort.</p>
<p>To explain Introsort, it is Quicksort most of the time, but
switches to Heapsort if the depth level gets degenerate (usually
set to "2 log n", where n is the list size - this tends to only
happen if the list is carefully crafted to defeat Quicksort), and
switches to Insertion Sort when a sublist gets to about 16 entries
in size, since while Insertion Sort is O(n²), it has much lower
overhead than Quicksort at this size and is hence faster. Unlike
the implementation in C++'s std::sort, I've noticed that it's
better to do the insertion sort right there and then because the
sublist will more likely still be in the cache; doing it as an end
step like std::sort I found is slower in Object Pascal, possibly
due to all the cache misses. I don't know if this is specific to
Object Pascal though. Something to make a benchmark for though.</p>
<p>Gareth aka. Kit</p>
<p>P.S. Because Quicksort, Heapsort and Insertion Sort are all
comparison sort algorithms, Introsort is also a comparison
algorithm overall, so it is still compatible with classes that
have a custom compare routine.<br>
</p>
<p><br>
</p>
<div class="moz-cite-prefix">On 05/06/2019 13:33, Michael Van
Canneyt wrote:<br>
</div>
<blockquote type="cite"
cite="mid:alpine.DEB.2.21.1906051429300.8202@home">
<br>
<br>
On Wed, 5 Jun 2019, J. Gareth Moreton wrote:
<br>
<br>
<blockquote type="cite">Still, saying all that, maybe there's room
for improvement in rtl-generics in the form of refactoring, like
I've found in the compiler itself in a few places. When you say
'heavyweight', do you mean it's a little slow sometimes or just
very bulky when it comes to code size? (Taking a brief look at
rtl-generics, there are a lot of classes!)
<br>
</blockquote>
<br>
<br>
rtl-generics is meant to be Delphi compatible, so be careful.
<br>
Also, Maciej did his best to make it as fast as possible. I doubt
you can
<br>
improve his code.
<br>
<br>
If you want to make improvements, I think fcl-stl and fgl units
are more amenable to that.
<br>
<br>
Michael.<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
fpc-devel maillist - <a class="moz-txt-link-abbreviated" href="mailto:fpc-devel@lists.freepascal.org">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
<div id="DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2"><br />
<table style="border-top: 1px solid #D3D4DE;">
<tr>
<td style="width: 55px; padding-top: 13px;"><a href="https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient" target="_blank"><img src="https://ipmcdn.avast.com/images/icons/icon-envelope-tick-round-orange-animated-no-repeat-v1.gif" alt="" width="46" height="29" style="width: 46px; height: 29px;" /></a></td>
<td style="width: 470px; padding-top: 12px; color: #41424e; font-size: 13px; font-family: Arial, Helvetica, sans-serif; line-height: 18px;">Virus-free. <a href="https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient" target="_blank" style="color: #4453ea;">www.avast.com</a>
</td>
</tr>
</table><a href="#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2" width="1" height="1"> </a></div></body>
</html>