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.
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.
Gareth aka. Kit
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.
On 05/06/2019 13:33, Michael Van Canneyt wrote:
On Wed, 5 Jun 2019, J. Gareth Moreton wrote:
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!)
rtl-generics is meant to be Delphi compatible, so be careful.
Also, Maciej did his best to make it as fast as possible. I doubt you can
improve his code.
If you want to make improvements, I think fcl-stl and fgl units are
more amenable to that.
Michael.
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
