DEV Community: Emura Daisuke

Introducing a fast multi-threaded memory allocator

Emura Daisuke — Thu, 03 Oct 2019 08:46:45 +0000

Liquid syntax error: 'raw' tag was never closed

Introduction of fast differential sorting algorithm "Homura-Shiki"

Emura Daisuke — Mon, 01 Apr 2019 05:56:37 +0000

焔式(Homura-Shiki)

Homura-Shiki is a new method of differential sort algorithm that applies merge sort.
For a sorted array, focus on the place where the value change is made and sort fast.

It has the following features.(Let D be the changed range)

Comparison sort
Stable sort
External area: N
Average time: O ((D log D) + N)
Worst time: O ((D log D) + N)
Best time: O (D)
Recursion: None

Source Code

Homura-Shiki(MIT License)

Basic algorithm

Change the value at any range in the sorted array.
Perform comparison stable sorting on the change range.
Merge three parcels in "Forward Range, Change Range, Rearward Range".

Examples

Change the value at any range in the sorted array.
0 2 3 4 5 6 7 9|Sorted array
    ↓↓↓
0 2|8 1 3|6 7 9|

Perform comparison stable sorting on the change range.
0 2|8 1 3|6 7 9|
    ↓↓↓
0 2|1 3 8|6 7 9|

Merge three parcels in "Forward Range, Change Range, Rearward Range".
0 2|1 3 8|6 7 9|

02   Forward Range
138  Change Range
679  Rearward Range

012    Merge with change range until there is no forward range.(Forward part)
36789  Merge the remainder of the change range with the rearward range.(Rearward part)

01236789  Join forward part and rearward part.(sort complete)

Build & Test

The following environment has been verified.

Windows 10 Pro 64bit
Core i7-8700 3.20GHz

Prepare Hayate-Shikli and Setsuna-Shiki in the sibling directory and build.

Msvc

Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27027.1 for x64

cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe

clang++

clang version 8.0.0 (tags/RELEASE_800/final)
Target: x86_64-w64-windows-gnu

clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe

g++

gcc version 8.3.0 (Rev2, Built by MSYS2 project)
Target: x86_64-w64-mingw32

g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe

Average benchmark

The following is the case of changing the random range of the sorted array to a random value.
The unit is seconds, the lower the number, the faster.

Msvc

Array	std::sort	std::stable_sort	Homura-Shiki
10,000	0.00031643	0.00016890	0.00014270
1,000,000	0.05004999	0.02833382	0.02414271
100,000,000	3.43509980	3.48550165	2.55574413

clang++

Array	std::sort	std::stable_sort	Homura-Shiki
10,000	0.00027717	0.00020017	0.00015642
1,000,000	0.03866672	0.02881882	0.02255046
100,000,000	3.38201222	3.64178056	2.60998679

g++

Array	std::sort	std::stable_sort	Homura-Shiki
10,000	0.00029155	0.00020019	0.00014887
1,000,000	0.04052708	0.02760306	0.02054782
100,000,000	3.58270940	3.45231729	2.36870185

Limited condition benchmark

The following is sorted by the array [100,000,000].
The unit is seconds, the lower the number, the faster.

Best case

When the range is specified randomly without changing the value for the sorted array.

	std::sort	std::stable_sort	Homura-Shiki
Msvc	0.23993706	1.30073792	0.01059685
clang++	1.04052412	1.52173567	0.01611595
g++	1.34400042	1.31273356	0.01510180

Finally

How was it?

We came up with the idea of differential sorting, in terms of the fact that sorting does not always have to be done in its entirety.
Although the comparison between std::sort and std::stable_sort, which is an overall sort, and Homura-Shiki, which is an diff sort, is not fair, it should be used to determine the usefulness of diff sort.

I think that it could be shown that sorting can be done faster by devising it.
As a guideline for operation, if (D <(N / 2)), differential sorting, otherwise it is a feeling that the whole sort is good.

The sort algorithm is still romantic.

Thanks for watching!

Proposal of a new method, Introduction of differential sort algorithm "Setsuna-Shiki"

Emura Daisuke — Sun, 24 Mar 2019 15:25:31 +0000

刹那式(Setsuna-Shiki)

Setsuna-Shiki is a new method of differential sorting algorithm that applies bisection insertion sorting.
For a sorted array, focus on the place where the value change is made and sort very fast.

It has the following features.

Comparison sort
Stable sort
External area: None
Average time: O (log N)
Worst time: O (log N)
Best time: O (2)
Recursion: None

Source Code

Setsuna-Shiki(MIT License)

Basic algorithm

Change the value at any position in the sorted array.
If (Changed position value < value below change position), the lower range is binary-searched and rotate from change position to search position.
If (value above change position < Changed position value), the upper range is binary-searched and rotate from change position to search position.

Examples

Change the value at any position in the sorted array.
0 1 2 4 5 6 7 9|Sorted array
        ↓
0 1 2 4 x 6 7 9|Change the value at any position

If (Changed position value < value below change position), the lower range is binary-searched and rotate from change position to search position.
0 1 2 4 5 3 7 9|In the case of [5]=3
0 1 2 4 5|. . .|Binary search the lower range
. . .|3 4 5|. .|Rotate from change position to search position
0 1 2 3 4 5 7 9|Sort result

If (value above change position < Changed position value), the upper range is binary-searched and rotate from change position to search position.
0 1 8 4 5 6 7 9|In the case of [2]=8
. . .|4 5 6 7 9|Binary search the upper range
. .|4 5 6 7 8|.|Rotate from change position to search position
0 1 4 5 6 7 8 9|Sort result

Points devised

Even if binary search is performed to the area where the same value is continuous, stability is maintained.

The binary search in the lower range searches the end of the continuous area.
The binary search in the upper range searches the beginning of a continuous area.

Build & Test

The following environment has been verified.

Windows 10 Pro 64bit
Core i7-8700 3.20 GHz

Msvc

Microsoft(R) C/C++ Optimizing Compiler Version 19.15.26732.1 for x64
Microsoft (R) Incremental Linker Version 14.15.26732.1

cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe

clang++

clang version 7.0.0 (tags/RELEASE_700/final)
Target: x86_64-w64-windows-gnu

clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe

g++

gcc version 8.2.0 (Rev3, Built by MSYS2 project)
Target: x86_64-w64-mingw32

g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe

Average benchmark

The following is the case of changing the random position of the sorted array to a random value.
The unit is seconds, the lower the number, the faster.

Msvc

Array	std::sort	std::stable_sort	Setsuna-Shiki
10,000	0.00007095	0.00004502	0.00000115
1,000,000	0.00975892	0.00698905	0.00009487
100,000,000	0.27018098	1.26169269	0.01670523

clang++

Array	std::sort	std::stable_sort	Setsuna-Shiki
10,000	0.00006162	0.00006669	0.00000050
1,000,000	0.00775640	0.00978430	0.00006938
100,000,000	0.99487866	1.46673092	0.01248609

g++

Array	std::sort	std::stable_sort	Setsuna-Shiki
10,000	0.00009420	0.00006123	0.00000040
1,000,000	0.01269281	0.00870394	0.00006129
100,000,000	1.32669707	1.32506381	0.01232715

Limited condition benchmark

The following is sorted by the array [100,000,000].
The unit is seconds, the lower the number, the faster.

Worst case 1

When changing the first to the maximum value for a sorted array.

	std::sort	std::stable_sort	Setsuna-Shiki
Msvc	0.28328255	1.27838705	0.03301556
clang++	0.94680632	1.49072315	0.02450915
g++	1.24406811	1.35104790	0.02465655

Worst case 2

When changing the end to the minimum value for a sorted array.

	std::sort	std::stable_sort	Setsuna-Shiki
Msvc	0.29024827	1.27097092	0.03784692
clang++	6.59369224	1.44779880	0.02844831
g++	7.05050788	1.30785120	0.02579642

Best case

When the position is specified randomly without changing the value for the sorted array.

	std::sort	std::stable_sort	Setsuna-Shiki
Msvc	0.26143167	1.24644350	0.00000026
clang++	0.99570890	1.44735863	0.00000031
g++	1.33114203	1.30589223	0.00000050

Finally

How was it?

We came up with the idea of differential sorting, in terms of the fact that sorting does not always have to be done in its entirety.
Although the comparison between std::sort and std::stable_sort, which is an overall sort, and Setsuna-Shiki, which is an diff sort, is not fair, it should be used to determine the usefulness of diff sort.

If you operate well, you can get a rapid performance, but if you use it incorrectly it will be a two-edged sword.

The sort algorithm is still romantic.

Thanks for watching!

Introduction of new comparison stable sorting algorithm

Emura Daisuke — Thu, 21 Mar 2019 06:40:15 +0000

颯式(Hayate-Shiki)

It has the following features.

Comparison sort
Stable sort
External area: N
Best: O (N)
Average: O (N log N)
Worst: O (N log N)
Recursion: None

Source Code

Hayate-Shiki(MIT License)

Basic algorithm

The external area is regarded as a 2N continuous band.
The following rules apply when placing values in the external area.
- If (maximum <= value), place it above the ascending order column and update the maximum.
- If (value < minimum), place it below the descending column and update the minimum.
- If (minimum <= value < maximum), place new values (maximum and minimum) in ascending order column, and let the value group arranged so far be Part.
Merge parts.

Examples

The external area is regarded as a 2N continuous band.

4 5 1 2 7 6 3 8|Input column
. . . . . . . .|External area
->Asc     Dsc<-|Actually

               |4 5 1 2 7 6 3 8|Input column
. . . . . . . . . . . . . . . .|External area
          Dsc<-|->Asc          |2N continuous band

Put new values (maximum and minimum) in ascending order column.
               |. 5 1 2 7 6 3 8
. . . . . . . . 4 . . . . . . .

The next value is (maximum <= value), place it above the ascending order column and update the maximum.
               |. . 1 2 7 6 3 8
. . . . . . . . 4 5 . . . . . .

The next value is (value < minimum), place it below the descending column and update the minimum.
               |. . . 2 7 6 3 8
. . . . . . . 1 4 5 . . . . . .

The next value is (minimum <= value < maximum), place new values (maximum and minimum) in ascending order column,
and let the value group arranged so far be Part.(Part: 145 completed)
               |. . . . 7 6 3 8
. . . . . . .|1 4 5|2 . . . . .

The next value is (maximum <= value), place it above the ascending order column and update the maximum.
               |. . . . . 6 3 8
. . . . . . .|1 4 5|2 7 . . . .

The next value is (minimum <= value < maximum), place new values (maximum and minimum) in ascending order column,
and let the value group arranged so far be Part.(Part: 27 completed)
               |. . . . . . 3 8
. . . . . . .|1 4 5|2 7|6 . . .

The next value is (value < minimum), place it below the descending column and update the minimum.
               |. . . . . . . 8
. . . . . . 3|1 4 5|2 7|6 . . .

The next value is (maximum <= value), place it above the ascending order column and update the maximum.(Part: 368 completed)
               |. . . . . . . .
. . . . . .|3|1 4 5|2 7|6 8|. .

External area result.
4 5|2 7|6 8|. .  Ascending column arrangement
. . . . . .|3|1  Descending column arrangement
4 5|2 7|6 8|3|1  Actual arrangement

Merge generated Parts.
145  27  368
12457  368
12345678
Sort complete.

Improvement

We will make additional improvements to the basic algorithm.

Insert sort is performed to secure the length of Part.
Merge sequentially to avoid recursion.

Environment that we verified

Windows 10 Pro 64bit
Core i7-8700 3.20 GHz
Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27030.1 for x64
clang version 8.0.0 (tags/RELEASE_800/final)
gcc version 8.3.0 (Rev2, Built by MSYS2 project)

Random number benchmark

Sorts float values generated from the same seed.
The unit is seconds, the lower the number, the faster.

Conditional benchmark

The following all sorted the array [100,000,000] of float value.
The unit is seconds, the lower the number, the faster.

Finally

How was it?

Hayate-Shiki is a stable sort, but has strong characteristics to random numbers.
In the conditional benchmark, it was found that the influence of the optimization characteristic of the compiler, rather than the algorithm characteristic, becomes strong, so that it can hardly be a judgment material.

Does it come the day when merge sort wins quick sort?

The sort algorithm is still romantic.

Thanks for watching!