For..Next..For What?

[G Gabriel]

Re: For..Next..For What?

This is quite weird!

[brett s]

Re: For..Next..For What?

OK, so wouldn't the "while...end while" structure suffer the same problem? (That's a retorical question). And personally, I have always had qualms about using the "if...then...else" construct, for the same reason. Too inefficient. And it's so easily avoided, just write out the code for every eventuality. Who cares about the duplication when we're only interested in speed of execution. In these days of multi-processor systems we can farm out each block of code to its own processor and the execution is completed in a mere pico second or two. And for that matter if branching is required we can throw in a few "go to"s - much more efficient than those high level constructs like "for" and "while" and "if" and "case" and "function" and ...

Or maybe for the ultimate in performance we should just ban looping constructs altogether. That's it, I'm off to the patent office. ;)

[G Gabriel]

Re: For..Next..For What?

Thanks Brett, I am with you, but I still can't explain this wierd phenomenon seen in the zip file attached.

Any explanation? anyone?

[DaveM]

Re: For..Next..For What?

the same basic code(while, do while, for, etc) is used in c, clipper and many others with minor variations. I have used it and seen others use it in a wide variety on languages.

I always thought it was copied once into memory and done in a split second at the base 0's and 1's. That is what I was taught was the fastest and gave a lot less code for the programmer to have to deal with.

I am not a proponent of Excel! There were other spreadsheets out there that it paled to in comparison, but got beat by the money. Borland made a great one.

Hey, I thought Alpha was written in C???

Dave Mason

[csda1]

Re: For..Next..For What?

I'll try to answer some questions that have been posted.

Alpha 5 is written primarily using a version of C (C++ or Visual C I think, but I could be wrong) for most of their key code. They also use a variety of purchased packages that add a variety of features (e.g AMI PDF drivers, RegEx, etc.) that could be coded in any language including assembly. Many of the UDF functions are coded in XBasic.

Timing Issues: Any timing measurement is only accurate to the PC's internal timing tic (1/18th of a second). The real time clock, accurate to miliseconds, is effectively only updated every timer tic, which really means that any timing number is only accurate to it's value +/- 1 timing tic, which means that a timing of 0.047 seconds is really .047 seconds +/- .055 seconds. The only way to improve this timing accuracy is to increase the time to a larger time by repeating the process many times and dividing by the iteration count. This is essentially what one of the functions on my new utility, the CSDA Code Utility , is made to do automatically. You can read some of it's documentation here.

The one issue that goes against the normal methods is common expression evaluation. It turns out that Alpha 5 Version 7 and earlier (It could change in future versions) actually have a high overhead in assignments (anything setting a variable, like X=57*3). If you had a common expression in more than one line, normally you would remove the common expression and execute it only once. But the overhead of the extra assignment is large compared to the time saved by doing it only once. E.g.

x=ADDMONTHS(DATE(),4)+15
y=ADDMONTHS(DATE(),4)+30
(2 assignments - execution time is .0000557 seconds)

vs

tmp=ADDMONTHS(DATE(),4)
x=tmp+15
y=tmp+30
(3 assignments - execution time is .0000945 seconds)

If common expression execution time is very large compared to the time of the extra assignment, then it makes sense to remove the common expression to calculate it only once in current versions of A5. But be warned, Alpha software knows this and it might change in a future version. But for now, it currently makes speed sense to expand an expression out.

Gabe: Changing a loop to multiple copies of the code is called "Unrolling a loop" and is one of many methods used by compilers and languages to speed up code. If the loop count is a constant, a good language can do this automatically. However, there are times when you must use a variable for the loop count. But let's say you knew the count was always even. You can then create a loop that has 2 copies oo the loop code, and divide the count by 2, resulting in half as many comparisons and increments. No language would ever figure out how to do this.

Loop unrolling and Loop-invariant_code_motion are the 2 most common techniques to improving loop speed. See some of the references below.

http://en.wikipedia.org/wiki/Optimiz...mputer_science)
http://en.wikipedia.org/wiki/Loop_optimization
http://en.wikipedia.org/wiki/Loop-invariant_code_motion
http://www.ibiblio.org/pub/languages/fortran/ch1-9.html


Brett:

OK, so wouldn't the "while...end while" structure suffer the same problem? (That's a retorical question). And personally, I have always had qualms about using the "if...then...else" construct, for the same reason. Too inefficient. And it's so easily avoided, just write out the code for every eventuality. Who cares about the duplication when we're only interested in speed of execution. In these days of multi-processor systems we can farm out each block of code to its own processor and the execution is completed in a mere pico second or two. And for that matter if branching is required we can throw in a few "go to"s - much more efficient than those high level constructs like "for" and "while" and "if" and "case" and "function" and ...

Actually, the loops (any type) are actually pretty efficient mechanisms. They can really translate into a very tight piece of machine code depending upon CPU type (x86 Intel for most of us) and how the loops are specified. WHILE loops are actually less efficient than FOR loops, but can be more general in their exit condition

Stan:

And there seems to be a script count of lines limit somewhere around 4840 lines, depeiding on the total character count I imagine.

Actually, I believe that's a script editor code limitation, and it is the same with the Interactive Window. With a different editor, that would/could change.

Unfamiliar with the "IW"

IW is the Interactive window of the code editor. I wouldn't use that acronym as it is not generally referred to that way in the Alpha community.

[G Gabriel]

Re: For..Next..For What?

Ira:
Thanks for the insights. Still, the question remains:
In the zip file attached, if you run the For..Next the first time, it's always slower the first time. The first time I saw that, I attributed it to difference in the computer speed and at which point you enter the "time cycle". But then, how come it's always slower the first time then faster thereafter?

In the "Unlooped" script, the difference cannot be attributed to any tic differences. It's quite a big difference.

So, two questions remain:
1-Why is it slower for either on the first time only
2-Why is it more manifest in the "unrolled" loop

Does alpha retain the script in cache after it ran the first time? If that is the case, Would defragmenting the script make it run faster?

[G Gabriel]

Re: For..Next..For What?

By the way, as to C:
Quite possibly alpha is written in C, but according to Selwyn, no user interface for the last 6 years or so, is written in C.

[MikeC]

Re: For..Next..For What?

G, Just a thought from a complete novice after reading the "Fortran" link Ira provided.

"Operating systems (except DOS) don't have to load all of your program
into memory during execution, the memory your program needs to store
code or data is partitioned into pages, and the pages are read and
written from and to the disk as necessary.

Computers use memory caches to reduce memory references. The cache is
a small and fast memory unit, when you reference a memory location,
the cache automatically saves the memory locations nearby. Later, if
you reference a memory location that happens to be in the cache it can
be brought much faster."

Could this be why the first run was slower than the succeeding ones?

Am responding only to perhaps save others time in doing so. In no way could my insights be as good as any that have responded so far!!! But am fascinated by the discussion nonetheless.

Mike

[G Gabriel]

Re: For..Next..For What?

Mike:

Could this be why the first run was slower than the succeeding ones?

That's my thinking as well, but I do not know that for a fact.
These snippets of information could help developers fine tune their scripts to optomize the speed particularly for complicated tasks, particularly on a server.

If the above is correct, it will answer one question, the other will remain: why is it much more prominent in the unrolled script when logic dictates otherwise?

[DaveM]

Re: For..Next..For What?

In the days of DOS, we assigned our memory addresses ourselves. This created great problems as memory usage grew and a lot of programs accessed memory at similar times(windows 3.1). Giving control of the memory to Windows was scary at first and did not always work, but later versions are much better. C is one of the closest languages to machine code( some one check that?) and causes a faster execution than most stuff. Visual Basic was/is written in C also. I do not believe Alpha uses Microsoft C++, but I do believe they use C++ by another maker or at least they did. Any program that is based on another would be slower that the original, but who wants to write the kind of stuff we do in C or C++? Alpha is trying very hard to make our efforts pay off with more functions, better interfaces and as much speed as possible. I believe that!

Dave Mason

[csda1]

Re: For..Next..For What?

The scripts being executed are cached, so there is some overhead loading it the 1st time (or anytime it is flushed from the cache). This is not significant except for short execution times.

Would defragmenting the script make it run faster?

I have no idea what you are refering to. There is no fragmentation of the code, and computer memory, string space cleanup etc. is nothing that is accessible at the XBasic level, and shouldn't matter.

The unrolled loop takes 0.09745098 seconds to execute. Compare that to the for-loop time of 0.13758333 seconds, a 50% increase in time, but no surprise.

By the way, as to C:
Quite possibly alpha is written in C, but according to Selwyn, no user interface for the last 6 years or so, is written in C.

User Interface code is not speed dependent, as a human is far slower than any computer, so what selwyn said is probably true (although there could be exceptions). What I said was that the key code (which is all underlying code that drives XBasic and everything else) that is written at Alpha Software is written in C.

Dave:

C is one of the closest languages to machine code( some one check that?)

That is a true statement, and that's why C is so popular. A high level language that can control the small stuff. Alpha creates relatively high level functions in it's language that in all the time sensitive areas are written in lower level languages, thus we get the "simplicity" of XBasic that gives great power at the high level with the speed of low level.

[G Gabriel]

Re: For..Next..For What?

Thanks Dave and Ira.
Dave, your contention is correct but I don't mean to write scripts in C to speed things up. If you take this a step further, you might as well eliminate Bill Gates and go straight to computer language!

What I mean is, knowing something as mundane as the fact that alpha cashes scripts, that could help write a more optimized script. By fragmenting the script I mean, if you know that alpha loads the script in cache and run it, then you could write only a smaller script to be loaded in cache and re-run it from cache thereafter for optimal speed.

It is not a common practice to re-run a script twice in a row. So, if you are running a script and if the first run is the slowest, the fact that the subsequent ones are a lot faster does not do you any good.

But that knowledge could be very invaluable in writing a script. In the example I used were instead of a for..next loop, you write consecutive lines of script, there is 2000 instances of a paired lines. Instead of running 4000 lines of commands, knowing that alpha will cache the script, I would run only the first two lines (this will be the slow run) then re-run them from the cache, may be using "goto" , and take advantage of the faster execution. That's what I meant by defragmenting the script.

This might look like we are talking about differences of melli-seconds, but in a large table this could save quite a bit of time and make the difference between seconds and minutes.

Here is another example:
while .not.eof()

Does that get evaluated once? stored in the cache? and tested in the cache? or does it get tested anew as you go from one record to the next? imagine doing that 100,000 or a million time!

[csda1]

Re: For..Next..For What?

As far as I can guess, each code object (script, function, event code - like an onpush) are loaded into a cache such that they are not re-read. Although untested, I would think that an entire form's events, and in fact the entire form object are loaded into "Alpha's cache", which is why someone else can edit a form while you are displaying it, and changes don't appear until the next reload of the form object.

So the bottom line is, an entire object (any type) is cached. The cache probably has no practical size limit for any code, and only get's thrown away or replaced when you force a reload of that object or write a new version of the object.

For speeding up any code, always look for the best algorithm (that matches the software abilities), use good coding techniques and lastly modify using optimization techniques like common expression removal (where it helps), loop unrolling etc.

[Marcel Kollenaar]

Re: For..Next..For What?

For speeding up any code, always look for the best algorithm (that matches the software abilities), use good coding techniques and lastly modify using optimization techniques like common expression removal (where it helps), loop unrolling etc.

@Ira, is common expression removal the same as factoring?

What is factoring? Factoring means organizing code into useful fragments. To make a fragment useful you often must separate reusable parts from no-reusable parts. The reusable part become new functions. I know a good book about Philosophy for Solving Problems, Thinking Forth, Leo Brodie!

[csda1]

Re: For..Next..For What?

Hi Marcel,

This could be just a nomenclature issue, but I consider factoring something like this;

x=(25*y)+(25*z)+(75*w)

which on most languages would be faster with

x=25*(y+z+(3*w))

Common expression removal is more like this

x=((y+z)*25)+(w**(y+z))

changes to

tmp=(y+z)
x=(tmp*25)+(w**tmp)

Note: the use of exponent operator **. There are no common factors, but there is a common sub-expression that can be evaluated once.

There are some expression evaluators that will pick up some of the common expressions, but not always. Some are even smart enough to recognize that y+z is the same as z+y. Many of them will perform constant trick substitutions like 4*x will instead be x shifted left 2 positions, or 3*w would be w+w+w depending upon the target system.

Any mathematical tricks you can use to simplify the number of steps to do an expression evaluation is generally a win (except for the A5 assignment overhead issue). Also anyone reading should learn to get familiar with RPN (Reverse Polish Notation), as that is the internal way expressions are evaluated (probably without exception).

Any Donald_Knuth books on Algorithms are also recommended highly.