search

jplevyak / dparser

A Scannerless GLR parser/parser generater.
https://github.com/jplevyak/dparser
BSD 3-Clause "New" or "Revised" License
105 stars 14 forks source link

Speed of dparser -- possibly increase with std::sort from C++? #16

Open mattfidler opened 5 years ago

mattfidler commented 5 years ago

For very long parsing blocks, the speed of dparser is long; See:

https://github.com/nlmixrdevelopment/RxODE/issues/61#issuecomment-456632859

The slowest function is here:

https://github.com/jplevyak/dparser/blob/98ae9ccd251c36c61a5ff2651e5c7ee1d0057ed3/parse.c#L854-L897

Which uses qsort

https://github.com/jplevyak/dparser/blob/98ae9ccd251c36c61a5ff2651e5c7ee1d0057ed3/parse.c#L864

In theory C++'s std::sort is 250% to 1000% faster and since you can refer to c++ from c, do you think a wrapper for the std::sort would greatly increase the parsing time?

If so, do you think it is worthwhile to contaminate the pure C with C++?

gonzus commented 4 years ago

My personal opinion (which carries whatever weight you wish to assign to it :-) ) is that no, this is not worthwhile, because it would bring in a dependency on the C++ development and runtime environments. One thing I love about dparser is its minimal requirements; they make it easier to use / wrap dparser wherever you wish.

mattfidler commented 4 years ago

You could also possibly use timsort which has some variants written in C.

froh commented 2 years ago

I just stumbled upon this inline variant of qsort in C: https://www.corpit.ru/mjt/qsort.html