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.

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

Std sort fails simple test case #657

Closed
Hejsil opened this Issue Dec 14, 2017 · 1 comment

Comments

Projects
None yet
2 participants
@Hejsil
Member

Hejsil commented Dec 14, 2017

Zig version: 0.1.1.c9e01412
This test fails:

const sort = @import("std").sort;
const debug = @import("std").debug;
const mem = @import("std").mem;

test "testSort" {
    var arr = []i32{ 5, 3, 1, 2, 4 };
    sort.sort(i32, arr[0..], sort.i32asc);

    for (arr) |item| debug.warn("{},", item);
    debug.assert(mem.eql(i32, arr, []i32{ 1, 2, 3, 4, 5 }))
}

sort result: 1,3,2,4,5

@andrewrk andrewrk added this to the 0.2.0 milestone Dec 14, 2017

@andrewrk andrewrk added the bug label Dec 14, 2017

@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Dec 15, 2017

Member

Goodness. Thanks for the test case.

There was another problem with the implementation of sort in the standard library, which is that it uses O(n) stack space via recursion. This is fundamentally insecure, especially if you consider that the length of an array you might want to sort could be user input. It prevents #157 from working as well.

I had a look at https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms and only 1 sorting algorithm checked all the boxes:

  • Best case O(n) complexity (adaptive sort)
  • Average case O(n * log(n)) complexity
  • Worst case O(n * log(n)) complexity
  • O(1) memory
  • Stable sort

And that algorithm is Block sort.

I found a high quality implementation of block sort in C, which is licensed under the public domain: https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.c

I ported the code from C to Zig, integrated it into the standard library, and it passed all tests first try. Amazing.

Surely, I thought, there must be some edge case. So I created a simple fuzz tester:

test "sort fuzz testing" {
    var rng = std.rand.Rand.init(0x12345678);
    const test_case_count = 10;
    var i: usize = 0;
    while (i < test_case_count) : (i += 1) {
        fuzzTest(&rng);
    }
}

var fixed_buffer_mem: [100 * 1024]u8 = undefined;

fn fuzzTest(rng: &std.rand.Rand) {
    const array_size = rng.range(usize, 0, 1000);
    var fixed_allocator = mem.FixedBufferAllocator.init(fixed_buffer_mem[0..]);
    var array = %%fixed_allocator.allocator.alloc(IdAndValue, array_size);
    // populate with random data
    for (array) |*item, index| {
        item.id = index;
        item.value = rng.range(i32, 0, 100);
    }
    sort(IdAndValue, array, cmpByValue);

    var index: usize = 1;
    while (index < array.len) : (index += 1) {
        if (array[index].value == array[index - 1].value) {
            assert(array[index].id > array[index - 1].id);
        } else {
            assert(array[index].value > array[index - 1].value);
        }
    }
}

This test passed as well. And so I think this problem is solved.

cc @stereosteve

Member

andrewrk commented Dec 15, 2017

Goodness. Thanks for the test case.

There was another problem with the implementation of sort in the standard library, which is that it uses O(n) stack space via recursion. This is fundamentally insecure, especially if you consider that the length of an array you might want to sort could be user input. It prevents #157 from working as well.

I had a look at https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms and only 1 sorting algorithm checked all the boxes:

  • Best case O(n) complexity (adaptive sort)
  • Average case O(n * log(n)) complexity
  • Worst case O(n * log(n)) complexity
  • O(1) memory
  • Stable sort

And that algorithm is Block sort.

I found a high quality implementation of block sort in C, which is licensed under the public domain: https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.c

I ported the code from C to Zig, integrated it into the standard library, and it passed all tests first try. Amazing.

Surely, I thought, there must be some edge case. So I created a simple fuzz tester:

test "sort fuzz testing" {
    var rng = std.rand.Rand.init(0x12345678);
    const test_case_count = 10;
    var i: usize = 0;
    while (i < test_case_count) : (i += 1) {
        fuzzTest(&rng);
    }
}

var fixed_buffer_mem: [100 * 1024]u8 = undefined;

fn fuzzTest(rng: &std.rand.Rand) {
    const array_size = rng.range(usize, 0, 1000);
    var fixed_allocator = mem.FixedBufferAllocator.init(fixed_buffer_mem[0..]);
    var array = %%fixed_allocator.allocator.alloc(IdAndValue, array_size);
    // populate with random data
    for (array) |*item, index| {
        item.id = index;
        item.value = rng.range(i32, 0, 100);
    }
    sort(IdAndValue, array, cmpByValue);

    var index: usize = 1;
    while (index < array.len) : (index += 1) {
        if (array[index].value == array[index - 1].value) {
            assert(array[index].id > array[index - 1].id);
        } else {
            assert(array[index].value > array[index - 1].value);
        }
    }
}

This test passed as well. And so I think this problem is solved.

cc @stereosteve

@andrewrk andrewrk closed this in 75ecfdf Dec 15, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment