2017/04/25

Method call optimization - skipping sort-applicable-methods

It's not that we don't sort methods. It's just that if we have only one applicable method, we don't need to call sort-applicable-methods at all. Obvious, right?

I thought it didn't matter, for that part is written in C (we call Scm_SortMethods) and it just returns without sorting at all when we have only one method. But lo and behold, it is quite effective. Here's the average of several runs, calling ref on a sparse vector 10M times.

Baseline:   3.065 real, 3.863 cpu
Optimized:  2.431 real, 2.793 cpu

Scm_SortMethods uses shell sort on C array to avoid allocation, and we have a setup overhead (convert list to array). That was a waste when we have only one method. And in many cases, we do.

Not bad for just a few lines of change.

https://github.com/shirok/Gauche/commit/556fee985246eed0dd0189b3763d662bf0b0075b

We could also optimize for the cases we have just two or three applicable methods, in which case we can use hard wired comparison instead of using general sorting. It depends on how often we get such cases; some benchmark is required.

Tags: 0.9.6, sort-applicable-methods