[fpc-devel] Standard generic classes

[J. Gareth Moreton]

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 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20190605/359549c6/attachment.html>