[Code review] Reordering an heavy array of cluster

[PinguX]

After spending a few more time on it, I managed to make it work correctly.

The solution was to avoid parallelism during the recursivity :

I don't know exactly why. I suppose it has to do with subVIs instantiation.

It is overall the slowest solution so far, as it doesn't scale well with the number of elements in the array/list.

~400ms for only 10k elements.

[drjdpowell]

I'm on holiday without a computer at the moment, but I note that the SQL solution to this is the phase "ORDER BY id1".

[PinguX]

---

@drjdpowell  a écrit :

I'm on holiday without a computer at the moment, but I note that the SQL solution to this is the phase "ORDER BY id1".

---

Yes, exactly.

Plus: the data I'm sortering come from a database on disk originally. So it definitely is a solution to keep in mind.

It is currently kept in memory and restructured because X and Y reasons.

(I wont explicitly list these reasons, sorry for the technical curiosity we sometime have here)

Whether or not I will have to abandon the data from memory and constantly read from the database again and again is a balance I'll have to make between X, Y and now Z (the sorting).

Or even keep the tables in memory, as BertMcMahan reminded. And adapt X and Y to the tables.

[drjdpowell]

I was nudging you in the direction of Bert's SQLite suggestion.  Though if you already have a capable database involved then consider leveraging that.  Generally, the more data manipulation and reduction one does at the database level the better.  I can't guess what your X and Y reasons are to juggle so much data in LabVIEW memory. 

[alexderjuengere]

---

@PinguX wrote:

After spending a few more time on it, I managed to make it work correctly.

The solution was to avoid parallelism during the recursivity :

I don't know exactly why. I suppose it has to do with subVIs instantiation.

It is overall the slowest solution so far, as it doesn't scale well with the number of elements in the array/list.

~400ms for only 10k elements.

---

you may also look into https://forums.ni.com/t5/Example-Code/Generic-sort-algorithms-for-LabVIEW/ta-p/3503232

it contains svereal sorting algorithms, also a merge sort

[PinguX]

---

@alexderjuengere  a écrit :

---

---

you may also look into https://forums.ni.com/t5/Example-Code/Generic-sort-algorithms-for-LabVIEW/ta-p/3503232

it contains svereal sorting algorithms, also a merge sort

---

So I made some more tries.

All the examples from the link are slower, I think it is due to the "less comparator" subVI, that must be called by reference.

The overhead of dynamic calls is significant.

Then I made a binary sort for the linked-list.

It is better than the "merge sort", about 6.5 times faster. But it's still far from others solutions.

Either I need to make recursive calls of subVI and the overhead kills me (merge sort), either I need to create a temporary array of DVR and make a tons of IPE structures calls to read/write the DVRs (binary sort).

I already knew that any data copying had to be avoided.

Now, I also know that calling VIs by reference is not suitable when responsiveness is required.

[Andrey_Dmitriev]

---

@PinguX wrote:

---

@alexderjuengere  a écrit :

---

---

you may also look into https://forums.ni.com/t5/Example-Code/Generic-sort-algorithms-for-LabVIEW/ta-p/3503232

it contains svereal sorting algorithms, also a merge sort

---

So I made some more tries.

All the examples from the link are slower, I think it is due to the "less comparator" subVI, that must be called by reference.

The overhead of dynamic calls is significant.

Then I made a binary sort for the linked-list.

It is better than the "merge sort", about 6.5 times faster. But it's still far from others solutions.

Either I need to make recursive calls of subVI and the overhead kills me (merge sort), either I need to create a temporary array of DVR and make a tons of IPE structures calls to read/write the DVRs (binary sort).

I already knew that any data copying had to be avoided.

Now, I also know that calling VIs by reference is not suitable when responsiveness is required.

---

With sorting, you have almost no chance of achieving competitive performance using pure LabVIEW code.

Implemented in Rust, tested on i7-4800MQ:

Benchmarking sorting algorithms on 100000 doubles

RustUnstable 3.4378ms
QuickSort 9.555ms
HeapSort 14.9951ms
MergeSort 22.647ms
InsertionSort 1.6340776s
SelectionSort 5.8352718s
BubbleSort 20.7521763s

Benchmarking sorting algorithms on 1000000 doubles

RustUnstable 41.3231ms
QuickSort 117.431ms
HeapSort 235.0164ms
MergeSort 260.5742ms

The native LabVIEW Sort 1D Array function performs somewhere between HeapSort and MergeSort.
But even that isn’t pure LabVIEW — it’s implemented in C/C++ under the hood.

Rust Code used in the benchmark above:

Spoiler

use rand::random;
use std::time::Instant;

// ------------------------------------------------------------
// Bubble Sort
// ------------------------------------------------------------
fn bubble_sort(arr: &mut [f64]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
        if !swapped {
            break;
        }
    }
}

// ------------------------------------------------------------
// Insertion Sort
// ------------------------------------------------------------
fn insertion_sort(arr: &mut [f64]) {
    for i in 1..arr.len() {
        let key = arr[i];
        let mut j = i;
        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1];
            j -= 1;
        }
        arr[j] = key;
    }
}

// ------------------------------------------------------------
// Selection Sort
// ------------------------------------------------------------
fn selection_sort(arr: &mut [f64]) {
    let n = arr.len();
    for i in 0..n {
        let mut min_idx = i;
        for j in i + 1..n {
            if arr[j] < arr[min_idx] {
                min_idx = j;
            }
        }
        arr.swap(i, min_idx);
    }
}

// ------------------------------------------------------------
// Merge Sort
// ------------------------------------------------------------
fn merge_sort(arr: &mut [f64]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }

    let mid = n / 2;
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    let mut merged = arr.to_vec();
    let (left, right) = (&arr[..mid], &arr[mid..]);

    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            merged[k] = left[i];
            i += 1;
        } else {
            merged[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        merged[k] = left[i];
        i += 1;
        k += 1;
    }

    while j < right.len() {
        merged[k] = right[j];
        j += 1;
        k += 1;
    }

    arr.copy_from_slice(&merged);
}

// ------------------------------------------------------------
// Quick Sort
// ------------------------------------------------------------
fn quick_sort(arr: &mut [f64]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(left);
    quick_sort(&mut right[1..]);
}

fn partition(arr: &mut [f64]) -> usize {
    let pivot = arr[arr.len() - 1];
    let mut i = 0;

    for j in 0..arr.len() - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, arr.len() - 1);
    i
}

// ------------------------------------------------------------
// Heap Sort
// ------------------------------------------------------------
fn heap_sort(arr: &mut [f64]) {
    let n = arr.len();

    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }

    for i in (1..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn heapify(arr: &mut [f64], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] > arr[largest] {
        largest = left;
    }
    if right < n && arr[right] > arr[largest] {
        largest = right;
    }

    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}

// ------------------------------------------------------------
// Rust Unstable Sort (built-in introsort)
// ------------------------------------------------------------
fn rust_unstable_sort(arr: &mut [f64]) {
    arr.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
}

// ------------------------------------------------------------
// Benchmark Helper
// ------------------------------------------------------------
fn benchmark(name: &str, mut data: Vec<f64>, sort_fn: fn(&mut [f64])) {
    let start = Instant::now();
    sort_fn(&mut data);
    let duration = start.elapsed();
    println!("{:<15} {:>10?}", name, duration);
}

// ------------------------------------------------------------
// Main
// ------------------------------------------------------------
fn main() {
    let size = 1_000_000;

    let original: Vec<f64> = (0..size)
        .map(|_| random::<f64>())
        .collect();

    println!("Benchmarking sorting algorithms on {} doubles\n", size);

    benchmark("RustUnstable", original.clone(), rust_unstable_sort);
    benchmark("QuickSort", original.clone(), quick_sort);
    benchmark("HeapSort", original.clone(), heap_sort);
    benchmark("MergeSort", original.clone(), merge_sort);

    // Slow algorithms (optional)
    // benchmark("InsertionSort", original.clone(), insertion_sort);
    // benchmark("SelectionSort", original.clone(), selection_sort);
    // benchmark("BubbleSort", original.clone(), bubble_sort);
}

/*
Benchmarking sorting algorithms on 100000 doubles i7 Haswell

RustUnstable      3.4378ms
QuickSort          9.555ms
HeapSort         14.9951ms
MergeSort         22.647ms
InsertionSort   1.6340776s
SelectionSort   5.8352718s
BubbleSort      20.7521763s

Benchmarking sorting algorithms on 1000000 doubles

RustUnstable     41.3231ms
QuickSort        117.431ms
HeapSort        235.0164ms
MergeSort       260.5742ms

*/

[BertMcMahan]

---

@PinguX wrote:

---

@alexderjuengere  a écrit :

---

---

you may also look into https://forums.ni.com/t5/Example-Code/Generic-sort-algorithms-for-LabVIEW/ta-p/3503232

it contains svereal sorting algorithms, also a merge sort

---

So I made some more tries.

All the examples from the link are slower, I think it is due to the "less comparator" subVI, that must be called by reference.

The overhead of dynamic calls is significant.

Then I made a binary sort for the linked-list.

It is better than the "merge sort", about 6.5 times faster. But it's still far from others solutions.

Either I need to make recursive calls of subVI and the overhead kills me (merge sort), either I need to create a temporary array of DVR and make a tons of IPE structures calls to read/write the DVRs (binary sort).

I already knew that any data copying had to be avoided.

Now, I also know that calling VIs by reference is not suitable when responsiveness is required.

---

Can you ingest the data in a format more suitable for sorting? If it was already a linked list, you wouldn't see the copy penalty. Though that won't work if your system needs to sort once per data import.

Also, you DID say this was already in a database- so can you not just retrieve it from the database already sorted?

[PinguX]

---

@BertMcMahan  a écrit :

---

---

Can you ingest the data in a format more suitable for sorting? If it was already a linked list, you wouldn't see the copy penalty. Though that won't work if your system needs to sort once per data import.

Also, you DID say this was already in a database- so can you not just retrieve it from the database already sorted?

---

The format can change. However, I have run out of ideas on what it should be, I can only think about : either one array of cluster, or multiple arrays, each containing a single data (integer, string, etc).

I think the issue with the linked list is not about copy. The data structure itself makes it difficult to sort, because it cannot be indexed the way an array can be.

As for retrieving the data from the database already sorted, I indeed said it was one of the solutions I'll have to compare.

Tomorrow, I will create simulation data in an SQLite file, in order to use James Powell's library.

I am optimistic.

[PinguX]

---

@PinguX  a écrit :

Tomorrow, I will create simulation data in an SQLite file, in order to use James Powell's library.

---

And here it is, attached.

For those who won't download :

~900ms to SELECT * (without ORDER BY)

~1030ms to SELECT * (with ORDER BY)

~70ms to order in LabVIEW (original sort of this post)

Everything is using the default configuration, 100k lines in the database file.

Perhaps there is a way to improve performance in SQLite ? (a setting to add ?)