mORMot Open Source

okoba

Member

Registered: 2019-09-29

Posts: 113

Multi thread sort

I am looking for different ways of achieving this, and I was wondering if people here have any insight or code.
PasMP and OmniThread have samples for it, but I am hoping for other info.

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,548

Website

Re: Multi thread sort

I have never needed this, because when sorting becomes a bottleneck, I usually change the algorithm, e.g. to store indexes instead of values, or use hashing, or use self-sorted structures.

What is your use case?
When are our QuickSort###() functions or TDynArray.Sort becoming too slow in practice?

okoba

Member

Registered: 2019-09-29

Posts: 113

Re: Multi thread sort

I have a list of log values (that I can not insert into SQLite, always changing and takes to much time to insert) and I want to query them using SQLite VTab, but as you know it can not use SQLite Index. So I thought about sorting them for xFilter to speedup order and group by. But for 100 million, it takes 8s to use the QuickSortInteger and more for string values.

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,548

Website

Re: Multi thread sort

If your result sets are not in the range of millions entries, I guess you could tune your algorithm.

You certainly don't need to sort all entries before getting the results.

For instance, a map/reduce/sort pattern may be better suited.
It would become a O(n) algorithm, not a O(log(n)), thanks to the "map/reduce" step.

okoba

Member

Registered: 2019-09-29

Posts: 113

Re: Multi thread sort

As I said I like to query the list using SQLite VTab and I can not change the algorithm of VTab if you mean that. SQLite xBestIndex asks for a ordered result to speedup order or group by and that is the reason I asked the question.