News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests

Main Menu

Implementing QuickSort

Started by UniverseIsASimulation, November 13, 2019, 04:30:41 AM

Previous topic - Next topic

UniverseIsASimulation

Hey, guys!
I am currently studying computer science and electrical engineering at the FERIT university in Osijek. So, for a seminar in algorithms and data structures, I've decided to attempt to implement QuickSort in my own simple low-level programming language, called AEC. You can see my work here:
https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort
So, the source code, written in AEC, is available here:
https://github.com/FlatAssembler/ArithmeticExpressionCompiler/blob/master/QuickSort/qsort.aec
The assembly my compiler (available for download here) produced is available here:
https://github.com/FlatAssembler/ArithmeticExpressionCompiler/blob/master/QuickSort/qsort.asm
The executable that FlatAssembler produced is available here:
https://github.com/FlatAssembler/ArithmeticExpressionCompiler/raw/master/QuickSort/qsort.exe
So, I've noticed that program is significantly slower than the programs produced by GCC.
Any idea how I can make it better?
Author of the AEC programming language:
https://flatassembler.github.io/compiler.html

jj2007

I had a quick look at qsort.asm - a detailed look is way beyond the time I can invest. What strikes my eye are numerous finit instructions. They are utterly slow. To give you an idea: One finit is over three times slower than measuring the length of a 100 byte string.

You should replace these finits with proper management of the fpu, i.e. ffree st(7), fstp st etc; where you consider finit essential, move it at least out of innermost loops.

UniverseIsASimulation

Quote from: jj2007 on November 13, 2019, 05:21:54 AM
I had a quick look at qsort.asm - a detailed look is way beyond the time I can invest. What strikes my eye are numerous finit instructions. They are utterly slow. To give you an idea: One finit is over three times slower than measuring the length of a 100 byte string.

You should replace these finits with proper management of the fpu, i.e. ffree st(7), fstp st etc; where you consider finit essential, move it at least out of innermost loops.
OK, thanks, I didn't know about that one with "finit".
Author of the AEC programming language:
https://flatassembler.github.io/compiler.html