< :前の番号
^ :番号順リスト
> :次の番号
P :前の記事（スレッド移動）
N :次の記事（スレッド移動）
|<:前のスレッド
>|:次のスレッド
^ :返事先
_:自分への返事
>:同じ返事先を持つ記事（前）
<:同じ返事先を持つ記事（後）
---:分割してスレッド表示、再表示
| :分割して（縦）スレッド表示、再表示
~ :スレッドのフレーム消去
.:インデックス
..:インデックスのインデックス
Issue #6256 has been updated by mame (Yusuke Endoh).
Status changed from Open to Assigned
Assignee set to MartinBosslet (Martin Bosslet)
Sound good. I agree, too.
Please create a patch and show benchmark.
--
Yusuke Endoh <mame / tsg.ne.jp>
----------------------------------------
Feature #6256: Slightly improve ruby_qsort performance
https://bugs.ruby-lang.org/issues/6256#change-25669
Author: MartinBosslet (Martin Bosslet)
Status: Assigned
Priority: Low
Assignee: MartinBosslet (Martin Bosslet)
Category: core
Target version: 2.0.0
Hi all,
I think I may have found a way to slightly improve the performance of ruby_qsort.
Quicksort running time is slightly decreased if the recursion depth (or in our
case, rather iteration depth) is bounded by leaving sub problems larger than or
equal to some cutoff bound k untouched and running Insertion Sort on these small
sub problems to finalize the sorting.
I experimented with this, but to no avail, only marginal improvements if any. Then
I remembered that instead of running Insertion Sort on each sub problem, it is
equivalent in terms of running time to run one single Insertion Sort on the whole
nearly sorted array as a final step. And in practice, this turns out to run faster
than without the optimization. In my tests, execution time dropped to about 95% on
average with an optimal cutoff (64-bit Fedora 15) [1].
Now this ain't the world - but it is faster, and I could very well imagine that there
is still room for improving my code. In my tests, the optimal cutoff seems to be ~13
for Integers and ~8 for Strings and Symbols. I imagine the more costly the comparisons,
the lower will be the optimal cutoff. I've tested only on 64 Bit yet, but I will do so
for 32 Bit, too.
If it turns out that this runs faster regardless of the architecture in use, with an
optimal cutoff yet to be determined, do you think this would be a useful addition?
I have attached a C extension for testing and discussing, it's mostly a one-to-one copy of
the code in util.c. I just added mmassign and insertion_sort plus the few lines that respect
the cutoff in rqsort (had to rename it, otherwise it would collide with the real "ruby_qsort").
-Martin
[1] https://github.com/emboss/hybridsort/blob/master/hybrid-sort-results
--
http://bugs.ruby-lang.org/