#StackBounty: #c++ #algorithm #assembly #mergesort #quick-sort HybridSort of QuickSort and MergeSort

Bounty: 50

I’ll try to publish a paper about the programming language I’ve made (ArithmeticExpressionCompiler, short AEC) in Osječki Matematički List and, in order to demonstrate its usability for implementing algorithms, I’ve tried to implement a fast sorting algorithm in it.

The basic idea of my algorithm is that QuickSort works better when the array is randomly-shuffled, while MergeSort works better when the array is already nearly sorted. Here it goes:

Syntax GAS ;Neka ArithmeticExpressionCompiler ispisuje asemblerski kod kompatibilan s GNU Assemblerom, da bude kompatibilan s GCC-om. Po defaultu ispisuje kod kompatibilan s FlatAssemblerom (a FlatAssembler na Linuxu ne radi bas najbolje).
verboseMode ON ;Neka ArithmeticExpressionCompiler ispisuje vise komentara u asemblerski kod koji ispisuje (da bude laksi za citanje i debuggiranje).
AsmStart ;Neka GNU Assembler obavijesti linkera da je "hybrid_sort" naziv potprograma...
    .global hybrid_sort
    hybrid_sort:
AsmEnd
If gornja_granica-donja_granica<2 ;Ako je niz duljine manje od 2 (0 ili 1), znaci da je vec poredan, pa prekidamo izvodenje ovog potprograma.
    AsmStart ;Kako radimo izvan sekcija, mozemo jednostavno prekinuti izvodenje potprograma asemblerskom naredbom "ret" (inace bismo, da radimo u sekcijama, morali znati vrti li se program na 32-bitnom ili 64-bitnom Linuxu).
        ret
    AsmEnd 
EndIf
razvrstanost:=0
i:=donja_granica
While i < gornja_granica - 1
    razvrstanost:=razvrstanost+(originalni_niz[i]<originalni_niz[i+1])
    i:=i+1
EndWhile
razvrstanost:=razvrstanost/((gornja_granica-donja_granica-1)/2)-1
i:=2
While i<7 | i=7 
    razvrstanost_na_potenciju[i] := pow(abs(razvrstanost), i) ;"pow(x,y)" je u AEC-u samo sintaksni secer za "exp(ln(x)*y)", i to vraca NaN za x=0 ili x<0. Nema ocitog nacina da se "pow(x,y)" prevede na asemblerski.
    razvrstanost_na_potenciju[i] := (razvrstanost=0) ? 0 : (mod(i,2)=1 & razvrstanost<0) ? (-razvrstanost_na_potenciju[i]) : razvrstanost_na_potenciju[i] ;C-ov i JavaScriptin uvjetni operator nekad zna znatno skratiti kod, zato sam ga ugradio i u svoj jezik.
    i:=i+1
EndWhile
;Formula koju je ispisao genetski algoritam za predvidanje koliko ce usporedbi QuickSort napraviti: https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort/Genetic_algorithm_for_deriving_the_formula
polinom_pod_apsolutnom := 2.38854*razvrstanost_na_potenciju[7] - 0.284258*razvrstanost_na_potenciju[6] - 1.87104*razvrstanost_na_potenciju[5] + 0.372637*razvrstanost_na_potenciju[4] + 0.167242*razvrstanost_na_potenciju[3] - 0.0884977*razvrstanost_na_potenciju[2] + 0.315119*razvrstanost
Eulerov_broj_na_koju_potenciju := (ln(gornja_granica - donja_granica) + ln(ln(gornja_granica - donja_granica))) * 1.05 + (ln(gornja_granica - donja_granica) - ln(ln(gornja_granica - donja_granica)) - ln(2)) * 0.9163 * abs(polinom_pod_apsolutnom)
koliko_usporedbi_ocekujemo_od_QuickSorta := exp(Eulerov_broj_na_koju_potenciju)
koliko_usporedbi_ocekujemo_od_MergeSorta := 2 * (gornja_granica - donja_granica) * ln(gornja_granica - donja_granica) / ln(2)
If razvrstanost=1 ;Ako je niz vec poredan.
    broj_vec_poredanih_podniza := broj_vec_poredanih_podniza + 1
    AsmStart
        ret
    AsmEnd
ElseIf razvrstanost = -1 ;Ako je niz obrnuto poredan...
    broj_obrnuto_poredanih_podniza := broj_obrnuto_poredanih_podniza + 1
    i:=donja_granica
    j:=gornja_granica-1
    While i<gornja_granica
        pomocni_niz[i] := originalni_niz[j]
        j := j - 1
        i := i + 1
    EndWhile
    i := donja_granica
    While i < gornja_granica
        originalni_niz[i] := pomocni_niz[i]
        i := i + 1
    EndWhile
    AsmStart
        ret
    AsmEnd
ElseIf koliko_usporedbi_ocekujemo_od_MergeSorta < koliko_usporedbi_ocekujemo_od_QuickSorta ;MergeSort algoritam (priblizno poredani podnizovi, za koje je MergeSort efikasniji od QuickSorta)...
    broj_pokretanja_MergeSorta := broj_pokretanja_MergeSorta + 1
    sredina_niza:=(gornja_granica+donja_granica)/2
    sredina_niza:=sredina_niza-mod(sredina_niza,1)
    vrh_stoga:=vrh_stoga+1 ;Zauzmi mjesta na stogu za rekurziju. Ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove. Da koristimo sistemski stog, morali bismo znati pokrecemo li se na 32-bitnom Linuxu ili 64-bitnom Linuxu, jer oni nisu kompatibilni u tom pogledu.
    stog_s_donjim_granicama[vrh_stoga]:=donja_granica
    stog_s_gornjim_granicama[vrh_stoga]:=gornja_granica
    stog_sa_sredinama_niza[vrh_stoga]:=sredina_niza
    gornja_granica:=sredina_niza
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica:=stog_s_donjim_granicama[vrh_stoga] ;Sad je rekurzija gotovo sigurno izmijenila sve globalne varijable koje nam trebaju ("donja_granica", "gornja_granica" i "sredina_niza"), ali zato imamo njihove stare vrijednosti na stogovima.
    gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
    sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
    donja_granica:=sredina_niza
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica:=stog_s_donjim_granicama[vrh_stoga]
    gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
    sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
    ;Spajanje nizova originalni_niz[donja_granica..sredina_niza] i originalni_niz[sredina_niza..gornja_granica] u jedan niz...
    i:=donja_granica
    gdje_smo_u_prvom_nizu:=donja_granica
    gdje_smo_u_drugom_nizu:=sredina_niza
    While i<gornja_granica
        If (gdje_smo_u_prvom_nizu=sredina_niza | originalni_niz[gdje_smo_u_drugom_nizu]<originalni_niz[gdje_smo_u_prvom_nizu]) & gdje_smo_u_drugom_nizu<gornja_granica
            pomocni_niz[i]:=originalni_niz[gdje_smo_u_drugom_nizu]
            gdje_smo_u_drugom_nizu:=gdje_smo_u_drugom_nizu+1
        Else
            pomocni_niz[i]:=originalni_niz[gdje_smo_u_prvom_nizu]
            gdje_smo_u_prvom_nizu:=gdje_smo_u_prvom_nizu+1
        EndIf
        i:=i+1
    EndWhile
    i:=donja_granica
    While i<gornja_granica
        originalni_niz[i]:=pomocni_niz[i]
        i:=i+1
    EndWhile
    vrh_stoga:=vrh_stoga-1 ;Oslobodi mjesto na stogovima.
    AsmStart
        ret
    AsmEnd
Else ;QuickSort algoritam (nasumicno ispremjestani podnizovi)...
    broj_pokretanja_QuickSorta := broj_pokretanja_QuickSorta + 1
    ;Daljnji kod je priblizno prepisan s https://www.geeksforgeeks.org/quick-sort/
    pivot := originalni_niz[gornja_granica - 1]
    i := donja_granica - 1
    j := donja_granica
    While j < gornja_granica - 1
        If originalni_niz[j] < pivot
            i := i + 1
            pomocna_varijabla_za_zamijenu := originalni_niz[i]
            originalni_niz[i] := originalni_niz [j]
            originalni_niz[j] := pomocna_varijabla_za_zamijenu
        EndIf
        j:=j+1
    EndWhile
    pomocna_varijabla_za_zamijenu := originalni_niz[i + 1]
    originalni_niz[i + 1] := originalni_niz[gornja_granica - 1]
    originalni_niz[gornja_granica - 1] := pomocna_varijabla_za_zamijenu
    gdje_je_pivot := i + 1
    vrh_stoga := vrh_stoga + 1 ;Zauzmi mjesta na stogu za rekurziju (ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove).
    stog_s_donjim_granicama[vrh_stoga] := donja_granica
    stog_s_gornjim_granicama[vrh_stoga] := gornja_granica
    stog_sa_sredinama_niza[vrh_stoga] := gdje_je_pivot
    gornja_granica := gdje_je_pivot
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica := stog_s_donjim_granicama[vrh_stoga]
    gornja_granica := stog_s_gornjim_granicama[vrh_stoga]
    gdje_je_pivot := stog_sa_sredinama_niza[vrh_stoga]
    donja_granica := gdje_je_pivot
    AsmStart
        call hybrid_sort
    AsmEnd
    vrh_stoga := vrh_stoga - 1 ;Oslobodi mjesto na stogovima.
    AsmStart
        ret
    AsmEnd
EndIf
AsmStart ;Ovdje tok programa ne smije doci. Ako dode, pozovi debugger.
    call abort
AsmEnd

The assembly code that my compiler produces can be seen here. It can be assembled using GNU Assembler, however, you won’t get an executable program from it. It’s just a routine that expects to be called from an external program. An example of such a program is here:

/*
 * Dakle, ovo ce biti omotac oko "hybrid_sort.aec" napisan u C++-u.
 * "hybrid_sort.aec" sam po sebi nije program koji se moze pokrenuti,
 * i zato cemo od C++ compilera (u ovom slucaju, GCC-a) traziti da
 * napravi program unutar kojeg ce se "hybrid_sort.aec" moze pokrenuti,
 * i, po mogucnosti, koji ce olaksati da ga testiramo. Drugim rijecima,
 * ovo je program s kojim se "hybrid_sort.aec" moze staticki linkirati.
 * */
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <iterator>

namespace AEC { // Da se razlikuju AEC-ove varijable od C++-ovih.
extern "C" {    // Za GNU Linker (koji se dobije uz Linux i koristi ga GCC), AEC
// jezik je dijalekt C-a, a moj compiler je C compiler.
float result, originalni_niz[1 << 16], kopija_originalnog_niza[1 << 16],
    pomocni_niz[1 << 16], i, gdje_smo_u_prvom_nizu, gdje_smo_u_drugom_nizu,
    gornja_granica, donja_granica, sredina_niza,
    stog_sa_sredinama_niza[1 << 10], stog_s_donjim_granicama[1 << 10],
    stog_s_gornjim_granicama[1 << 10], vrh_stoga, pomocna_varijabla_za_zamijenu,
    gdje_je_pivot, j, pivot, koliko_usporedbi_ocekujemo_od_QuickSorta,
    koliko_usporedbi_ocekujemo_od_MergeSorta, razvrstanost,
    Eulerov_broj_na_koju_potenciju, polinom_pod_apsolutnom,
    razvrstanost_na_potenciju[8],
    broj_vec_poredanih_podniza = 0, broj_obrnuto_poredanih_podniza = 0,
    broj_pokretanja_MergeSorta = 0,
    broj_pokretanja_QuickSorta =
        0; // GNU Linker omogucuje da se varijable ne deklariraju ne samo u
           // razlicitim datotekama, nego i u razlicitim jezicima. Znaci, ne
           // moram traziti kako se, recimo, na 64-bitnom Linuxu deklariraju
           // globalne varijable na asemblerskom jeziku, jer GCC to vec zna.
void hybrid_sort(); //".global hybrid_sort" iz "hybrid_sort.aec". U C++-u ga
// morate deklarirati da biste ga mogli koristiti. C++ nije
// kao JavaScript ili AEC u tom pogledu, C++ pokusava pronaci
// krivo natipkana imena varijabli i funkcija vec za vrijeme
// compiliranja.
}
} // namespace AEC
const int n = 1 << 16;

int main() {
  std::cout << "sortednesstsorted_arraytreversetMergeSorttQuickSortn";
  for (int i = 0; i < n; i++)
    AEC::originalni_niz[i] = i;
  for (int i = 0; i <= n; i += 1 << 9) {
    std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    if (i < (n / 2))
      std::reverse(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    int broj_ispremjestanja = abs(i - (n / 2)) * 1.5;
    for (int j = 0; j < broj_ispremjestanja; j++)
      std::iter_swap(&AEC::originalni_niz[std::rand() % n],
                     &AEC::originalni_niz[std::rand() % n]);
    if (!(rand() % 100))
      std::random_shuffle(
          &AEC::originalni_niz[0],
          &AEC::originalni_niz[n]); // Ponekad namjesti da poredanost bude nula.
    if (!(rand() % 100))
      std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                [](float a, float b) -> bool {
                  return a > b;
                }); // Ponekad namjesti da poredanost bude 1. Za to sam koristio
                    // C++-ove lambda funkcije. Njih GCC podrzava jos od 2007, a
                    // komercijalni compileri jos od ranije. Nadam se da netko
                    // nece pokusati ukucati ovo u neki arhaican compiler.
    float razvrstanost = 0;
    for (int j = 0; j < n - 1; j++)
      razvrstanost += AEC::originalni_niz[j] < AEC::originalni_niz[j - 1];
    razvrstanost = razvrstanost / ((n - 1) / 2) - 1;
    std::copy_n(&AEC::originalni_niz[0], n, &AEC::kopija_originalnog_niza[0]);
    AEC::broj_vec_poredanih_podniza = 0;
    AEC::broj_obrnuto_poredanih_podniza = 0;
    AEC::broj_pokretanja_MergeSorta = 0;
    AEC::broj_pokretanja_QuickSorta = 0;
    AEC::gornja_granica = n;
    AEC::donja_granica = 0;
    AEC::vrh_stoga = -1;
    AEC::hybrid_sort();
    std::sort(&AEC::kopija_originalnog_niza[0],
              &AEC::kopija_originalnog_niza[n]);
    if (!std::equal(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                    &AEC::kopija_originalnog_niza[0])) {
      std::cerr << "C++-ov std::sort nije dobio isti rezultat za i=" << i << '!'
                << std::endl;
      return 1; // Javi operativnom sustavu da je doslo do pogreske.
    }
    std::cout << razvrstanost << 't'
              << std::log(1 + AEC::broj_vec_poredanih_podniza)
              << 't' // Broj vec poredanih podniza moze biti i nula (ako je,
                      // recimo, razvrstanost jednaka -1), a, kako logaritam od
                      // nula ne postoji, dodat cu jedinicu da se program ne rusi
                      // na nekim compilerima.
              << std::log(1 + AEC::broj_obrnuto_poredanih_podniza) << 't'
              << std::log(1 + AEC::broj_pokretanja_MergeSorta) << 't'
              << std::log(1 + AEC::broj_pokretanja_QuickSorta) << 'n';
  }
  std::flush(std::cout); // Obrisi meduspremnik prije no sto zavrsis program.
  return 0; // Javi operativnom sustavu da je program uspjesno zavrsen.
}

I am interested in how I can make it better. I notice it’s not nearly as fast as the C++ std::sort.

Here are some measurements I’ve made:

I’ve also tried to diagnose the performance problems by measuring how often each algorithm is used for an array of specific sortedness:

But I still can’t figure out what’s exactly slowing it down to be more than 100 times slower than C++ std::sort is. Can you figure it out? Or can you make my code better in some other way?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.