Mad_guy

Hey guys, I just finished maybe the best, -and most advanced- Assembly program I've ever written.

It's basically a permutation program that generates aaaa through zzzz, it's nothing special, really. I was just talking to a friend, Tonto, when he mentioned his one written in C, and he said it was shitty and needed optimizations. He kinda 'challenged' me to write on in Assembly, so, I gave it a whirl.


The code is messy, unorganized, and totally overall sloppy. But it's the very first permutation program I've written ever, still, I like it.

I haven't clocked it yet against Tonto's, but it looks much faster, but a lot less easier to read than his (links are to follow.)



Without further ado:
Tonto's Permutation Program, written in C.
My Permutation Program, written in Assembly.

Also note, my code was made and compiled with Emu8086.

Ooble

Looks great. I might write one myself and see if I can get it to run faster.

__________________
Me :: You :: Them

Mad_guy

You probably can if you've ever done it before in some other language.


As far as I'm concerned, that code is extremely sloppy, and I probably could have whipped up a better algorithm to do the same thing. But, this is the first time I've ever done Permutation, and Assembly is the last language I ever expected to do my first one in. I always concidered myself to really suck ass at Assembly, but now I feel as if I suck less at it.


Also note, comments get on my nerves sometimes.

Also, code updated, there were a few things I didn't catch earlier.



And because I'm on a generally shitty OS, I can't run both mine and my friends program at the same time, since apparently WinME gives the current 'front' application the biggest timeslice, but my friend Tonto said his takes around 25 seconds to get finished while mine got done in about 10, I really can't verify this myself though.

lostcauz

Good job Mad_guy.

__________________
-- lostcauz

Stepped in what?...
Behind whose barn?...
I didn't even know they had a cow!

Mad_guy

Heh, thanks. Whole thing took around an hour to make. I can't say I enjoyed thinking up the algo and then having to rethink it to get everything to work properly though... But that's something you gotta deal with in Assembly I guess.


Now I need to make something else... Maybe an ATBASH or Caesar Shift cipher implementation...

DaWei

I haven't looked at your asm version, but the C implementation is both inefficient and doesn't terminate properly. You're being unfair to yourself by outputting the steps, as you have no control over whether the I/O is written for optimum performance or whether one implementation you run your code on has more work to do to get the output displayed. I recommend, once you're past the debug mode, that you measure performance with no output. Bear in mind that on most typical modern operating systems, you're in a multiprocessing environment where cpu time can be unilaterally taken away from your code and given to other processes. One run may be much worse than another. The other guy's code may get a "good" set of circumstances and yours may get worse. If you can't guarantee yourself 100% of the processor's attention, make a large number of runs for each and take an average. Given the number of permutations for a 5-element string, each of which has 26 possible values, it could take a very long time to make multiple runs. Your algorithm can be judged just as accurately and much more quickly (for comparison purposes) by reducing the length of the string to 2 or 3.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

lostcauz

Realtime_priority_class

__________________
-- lostcauz

Stepped in what?...
Behind whose barn?...
I didn't even know they had a cow!

DaWei

I would recommend against setting a high priority, and certainly realtime priority. It seems like a good idea at first to just seize the processor's undivided attention, but it doesn't work well in practice. The OS has been DESIGNED to keep tabs on things and control multiple processes with processes of its own. Locking them out would cause untoward things to happen. Realtime priority puts the code in approximately the same class as would kernel-level code with an interrupt-service routine. The deal is, when you get your high-priority time, do only what must be done, do it as rapidly as possible, set flags or conditions to enable further low-priority processing, and get the hell out.

The little program under consideration would lock up the machine for massive amounts of time. If it were a critical design study one would put it on a micro and run it raw, sans any type of OS, or invest in a really good (expensive) profiler. Probably the best approach for this level of investigation is multiple runs so that the apps being compared get approximately equal attention (however much attention that amounts to) as fluctuations average out.

Priorities in multitasking OSs seem to run counter to intuition at first, until you think about them with more machine-oriented familiarity. Writing one is a great learning exercise. Here is an example: the secretary preparing a document on a really busy multi-user machine considers his/her task to be the "foreground" task, brooking no delays because of silly things like DB queries and so forth. In reality, it's a very low priority task because the processor can handle the highest rate of keystrokes while practically asleep.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

lostcauz

Hi DaWei,

Welcome to programmingforums. While I might agree that the use of higher priority in this case is not necessary, I do not agree with your statements concerning the use of them. It is standard practice for many assembly programmers to use REALTIME for benchmarking. This minimizes the number of interfering interrupts and tends to eliminate some of the variance that can be experienced when performing such a test. On win95/98 the interrupts can be turned off thus offering even more accuracy.

First you should determine the timing overhead for the processor you are using. After setting the REALTIME priority and initializing the fpu along with any user initializations, you can use the rdtsc instruction to read the clock counter. Save the start time, serialize (cpuid), run your test code, serialize, read clock, store the count, calculate and retrieve the results.

__________________
-- lostcauz

Stepped in what?...
Behind whose barn?...
I didn't even know they had a cow!

DaWei

Win95/98 are not preemptive. Consequently, system chores (if any) tend to be wrapped up and clean when handover is made to an app. Same is true of even older versions which ran in real mode. Preemptive OSes, and particularly multiuser systems, are a horse of a different color. I would suggest that you do whatever you wish. If your knowledge of the system is great enough, you'll probably survive.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers