Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

fix: new sorting algorithm #1904

Merged
merged 33 commits into from
Jul 12, 2021
Merged

fix: new sorting algorithm #1904

merged 33 commits into from
Jul 12, 2021

Conversation

MaxGraey
Copy link
Member

@MaxGraey MaxGraey commented Jun 14, 2021 •
edited
Loading

New sorting algorithm based on "Power Sort" from "Nearly-Optimal Mergesorts" (May 2018) paper (https://arxiv.org/pdf/1805.04154.pdf). Also this implementation contains highly optimized novel insertion sort as part of main algorithm.

The previous algorithm was unstable which forced us to do fallback on the slow insertion sort for reference types for following ECMAScript spec. Which, of course, was very undesirable.

Features:

  • Stable

  • Faster than TimSort (approx 1.5-2x)

  • Faster than JS sort (TimSort) (approx 5x)

  • Has a mathematical proof of correctness, unlike TimSort (See paper)

  • I've read the contributing guidelines

@MaxGraey MaxGraey requested a review from dcodeIO June 14, 2021 18:06
@MaxGraey MaxGraey marked this pull request as ready for review June 14, 2021 18:07
@MaxGraey
Copy link
Member Author

MaxGraey commented Jun 28, 2021 •
edited
Loading

Benchmark sources:

AssemblyScript & JavaScript:
https://webassembly.studio/?f=8ehyqora2yn

Rust wasm:
https://webassembly.studio/?f=dfp7z1h91q8

Results:

Chrome 91

AS sort 100_000 doubles : 18.70 ms
AS sort 10_000_000 doubles: 5168.00 ms

AS NEW sort 100_000 doubles : 11.30 ms
AS NEW sort 10_000_000 doubles: 1591.20 ms

Rust (wasm) sort 100_000 doubles : 19.80 ms
Rust (wasm) sort 10_000_000 doubles: 2300.60 ms

JS sort 100_000 doubles : 43.20 ms
JS sort 10_000_000 doubles: 7835.60 ms

Firefox 89

AS sort 100_000 doubles : 22.00 ms
AS sort 10_000_000 doubles: 5436.00 ms

AS NEW sort 100_000 doubles : 12.00 ms
AS NEW sort 10_000_000 doubles: 1946.00 ms

Rust (wasm) sort 100_000 doubles : 23.00 ms
Rust (wasm) sort 10_000_000 doubles: 2793.00 ms

JS sort 100_000 doubles : 33.00 ms
JS sort 10_000_000 doubles: 4760.00 ms

Safari 14.2 TP

AS sort 100_000 doubles : 21.00 ms
AS sort 10_000_000 doubles: 5034.00 ms

AS NEW sort 100_000 doubles : 16.00 ms
AS NEW sort 10_000_000 doubles: 1876.00 ms

Rust (wasm) sort 100_000 doubles : 27.00 ms
Rust (wasm) sort 10_000_000 doubles: 2432.00 ms

JS sort 100_000 doubles : 23.00 ms
JS sort 10_000_000 doubles: 2792.00 ms

@JairusSW
Copy link
Contributor

Yayy!

dcodeIO
dcodeIO reviewed Jul 2, 2021
View reviewed changes
Copy link
Member

@dcodeIO dcodeIO left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can't really comment on the algorithm yet, but have a few more general comments :)

std/assembly/util/sort.ts Outdated Show resolved Hide resolved
std/assembly/util/sort.ts Outdated Show resolved Hide resolved
std/assembly/util/sort.ts Outdated Show resolved Hide resolved
std/assembly/util/sort.ts Outdated Show resolved Hide resolved
@MaxGraey MaxGraey mentioned this pull request Jul 7, 2021
Closed
@MaxGraey MaxGraey merged commit 6b774d4 into AssemblyScript:main Jul 12, 2021
@MaxGraey MaxGraey deleted the new-sort branch July 12, 2021 05:47
romdotdog pushed a commit to romdotdog/assemblyscript that referenced this pull request Jul 19, 2021
@MaxGraey @romdotdog
fix: new sorting algorithm (AssemblyScript#1904)
b6c30f4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@dcodeIO dcodeIO dcodeIO approved these changes

Assignees
No one assigned
Labels
compatibility enhancement performance standard library
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@MaxGraey @JairusSW @dcodeIO