diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | config.asm | 2 | ||||
| -rw-r--r-- | makefile | 12 | ||||
| -rwxr-xr-x | optim.sh | 53 | ||||
| -rw-r--r-- | readme.md | 22 | ||||
| -rw-r--r-- | sort.asm | 4 |
6 files changed, 83 insertions, 12 deletions
@@ -3,3 +3,5 @@ sort.o data.o csort.o csort + +*.asme @@ -1,2 +1,2 @@ -%define USE_SYSCALL 0 +%define USE_SYSCALL 1 ; better for most arrays %define TIMEOUT 1 @@ -1,11 +1,11 @@ all: asm asm: - @nasm -f elf64 -o sort.o sort.asm - @nasm -f elf64 -o data.o data.asm - @gcc -no-pie -o sort data.o sort.o + @nasm -O3 -f elf64 -o sort.o sort.asm + @nasm -O3 -f elf64 -o data.o data.asm + @gcc -O3 -no-pie -o sort data.o sort.o c: - @nasm -f elf64 -o data.o data.asm - @gcc -no-pie -c -o csort.o benchmark/sort.c - @gcc -no-pie -o csort data.o csort.o + @nasm -O3 -f elf64 -o data.o data.asm + @gcc -O3 -no-pie -c -o csort.o benchmark/sort.c -Wno-pointer-to-int-cast + @gcc -O3 -no-pie -o csort data.o csort.o diff --git a/optim.sh b/optim.sh new file mode 100755 index 0000000..04accf9 --- /dev/null +++ b/optim.sh @@ -0,0 +1,53 @@ +#!/bin/bash + +TRIALS=100 +SUCCESSES=10 + +echo "if this takes too long, either choose a random timeout from the trials, adapt the script accordingly, or just use smaller numbers hehe" + +set -e + +make c +REFERENCE=$(./csort) + +function test() { + make asm + for i in $(seq $TRIALS); do + output=$(stdbuf -i0 -o0 -e0 ./sort) + if [ "$output" != "$REFERENCE" ]; then + return 1 + fi + done + return 0 +} + +function substitute() { + sed -ie "/^%define TIMEOUT/s/ [0-9]\+/ $1/" config.asm +} + +# TODO: Multithreading +minimum=4294967295 +successes=0 +timeout=1 +while true; do + substitute $timeout + if test; then + successes=$((successes + 1)) + echo "$successes/$SUCCESSES with $timeout" + + if [ $timeout -le $minimum ]; then + minimum=$timeout + fi + + if [ $successes -eq $SUCCESSES ]; then + break + fi + + timeout=$((timeout - timeout / 3)) + else + timeout=$((timeout * 2)) + fi +done + +substitute $minimum +echo "Done. Timeout $minimum will probably work most of the time." @@ -2,9 +2,20 @@ > efficiently sleeping with (sub-)nanosecond precision and asm threads +## Benchmarks + +With *good* numbers and *optimized* timeouts, sleepsort can achieve +similar performance as C’s `qsort`. + +Example using the included array in `data.asm`: + +``` bash +time ./sort # real 0.008s +time ./csort # real 0.002s +``` + ## Dependencies -- ed - nasm - gcc - make @@ -12,7 +23,12 @@ ## Usage ``` bash -ed sort.asm # edit array and choose coolsleep/boringsleep -make +$EDITOR data.asm # edit array +$EDITOR config.asm # choose syscall/busyloop strategy +./optim.sh # find optimal sleep timeout ./sort ``` + +## Usefulness + +None @@ -32,7 +32,7 @@ end: ; uses nanosleep syscall sleep: - mov rax, TIMEOUT ; 0x424242 + mov rax, TIMEOUT mov rcx, rsi mul rcx push qword rax ; ns @@ -48,7 +48,7 @@ sleep: ; uses busy loop sleep: - mov rax, TIMEOUT ; 0x4242424 + mov rax, TIMEOUT mov rcx, rsi mul rcx .loop: |