Runtime error

[440bx]

For dynamic arrays, however, Low always returns 0, and High always returns the length minus one. This implies that for an empty array High returns -1 (which, when you think about it, is a strange value, as it is lower than that returned by Low).

Low, High => 2 functions calls vs Length => 1 call in performance terms.

Correctness and ease of maintenance are much, much more important than saving a few clock cycles and opening the door to bugs by forgetting to subtract 1.

If you want performance, learn algorithms that can be parallelized.  That will make a difference, the few clock cycles you saved while opening the door to typing mistakes won't.

and talking about mistakes... there aren't two (2) function calls as you believe/stated, only one (1) to set High. The code generated by the compiler is:

Code: Pascal  [Select][+][-]

1. fpc_dynarray_high
2. 0040A4B0 85c0                     test   %eax,%eax
3. 0040A4B2 7405                     je     0x40a4b9 <fpc_dynarray_high+9>
4. 0040A4B4 8b40fc                   mov    -0x4(%eax),%eax
5. 0040A4B7 eb05                     jmp    0x40a4be <fpc_dynarray_high+14>
6. 0040A4B9 b8ffffffff               mov    $0xffffffff,%eax
7. 0040A4BE c3                       ret    
8.  

That's in the ballpark of thirty (30) clock cycles.  Savings of 30 clock cycles are not the way of making a program faster.

[julkas]

I have started Pascal programming with problems on SPOJ a few months ago. So the first thing that comes to mind is performance.

I am  learning.

Thanks.

BTW
Quote is from Marco Cantù "Object Pascal Handbook".
I never use Low, High on dynamic arrays. May be it's my mistake. Who knows? Enlighten me, please.

[ASerge]

By the way, it is strange that FPC does not inlining the "High" call, but inlining the "Length" call. By the code below, the Length function is even longer:

Code: Pascal  [Select][+][-]

1. function fpc_dynarray_length(p : pointer) : tdynarrayindex;[Public,Alias:'FPC_DYNARRAY_LENGTH']; compilerproc;
2.   begin
3.      if assigned(p) then
4.        fpc_dynarray_length:=pdynarray(p-sizeof(tdynarray))^.high+1
5.      else
6.        fpc_dynarray_length:=0;
7.   end;
8.  
9.  
10. function fpc_dynarray_high(p : pointer) : tdynarrayindex;[Public,Alias:'FPC_DYNARRAY_HIGH']; compilerproc;
11.   begin
12.      if assigned(p) then
13.        fpc_dynarray_high:=pdynarray(p-sizeof(tdynarray))^.high
14.      else
15.        fpc_dynarray_high:=-1;
16.   end;

[julkas]

By the way, it is strange that FPC does not inlining the "High" call, but inlining the "Length" call.

Good. So the question is - what is the best approach for iterate and assign (in terms of performance)?

Code: Pascal  [Select][+][-]

1. for i := 0 to Length(Data)-1 do

Code: Pascal  [Select][+][-]

1. for i := Low(Data) to High(Data) do

Code: Pascal  [Select][+][-]

1. for x in Data do

[lucamar]

Good. So the question is - what is the best approach for iterate and assign (in terms of performance)?

It's not only a question of performance. Suppose you have a procedure with this signature:

Code: [Select]

procedure DoSomething(AnArray: Array of Integer);
What do you think happens if you call it like:

Code: Pascal  [Select][+][-]

1. var
2.   MyArray: array[5..15] of Integer;
3. begin
4.   FillArray(MyArray); { Fills the array }
5.   DoSomething(MyArray);
6. end;

Hint: Try the three alternatives and make it show Low(AnArray) and High(AnArray)

[440bx]

I have started Pascal programming with problems on SPOJ a few months ago. So the first thing that comes to mind is performance.

I am  learning.

Thanks.

BTW
Quote is from Marco Cantù "Object Pascal Handbook".
I never use Low, High on dynamic arrays. May be it's my mistake. Who knows? Enlighten me, please.

You're welcome. I suggest you take performance a few notches down the totem pole.

The best performance is derived from selecting good algorithms.  That's what being a good programmer is about, having a large bank of algorithms in your head and selecting the one that best fits the problem at hand.

Optimizing code is the compiler's job, not the programmer's.  It seems not very many programmers realize that.

I suggest you read these two books:

1. Algorithms by Robert Sedgewick.  The second edition - which you can get quite cheap - presents the algorithms in Pascal pseudocode.  Later editions are C "flavored".

2. Brinch Hansen On Pascal compilers.  Teaches you how to write a compiler but, if you really pay attention, you'll find that it is a lot more than about writing compilers.  IMO, there is no book that comes even close to teaching as much about programming than that book does.  Unfortunately, it is a bit pricey even used but, it's worth its weight in gold (if you read it attentively, that is.)

After those, select books written by people who have a solid background in computer science.  John Bentley's books "programming pearls" are excellent reads too.   To learn Pascal, I always recommend "oh Pascal" from Doug Cooper, an excellent book, superb programming advice.

As far as the use of "low" and "high".  The thing to always keep in mind is, does the compiler offer something that would prevent a mistake ?.  When the answer is yes then use that even if it costs a few extra clock cycles, you got roughly 3 billion of them per second, a few clock cycles here and there will not make any humanly perceptible difference but, they'll make a big difference when you forgot to subtract 1 because you didn't want to spend them.

Best advice I can give any programmer: put performance after maintainability and ease of understanding the code.  You'll appreciate it when you look at your own code again, a year later and, it isn't full of "tricks" to save a cheap processor the burden of spending a few clock cycles to make your life easier.  Make that CPU for you, don't work for the CPU.

Lastly, spend your time commenting your code.  What is obvious to you when you're writing the program is unlikely to be obvious a year or two later when you're trying to add a feature or fix a bug.  You'll appreciate having spent the time commenting what seemed obvious then.


@Serge

Yes, it is interesting that it doesn't inline High.

[julkas]

1. Algorithms by Robert Sedgewick.  The second edition - which you can get quite cheap - presents the algorithms in Pascal pseudocode.  Later editions are C "flavored".

2. Brinch Hansen On Pascal compilers.  Teaches you how to write a compiler but, if you really pay attention, you'll find that it is a lot more than about writing compilers.  IMO, there is no book that comes even close to teaching as much about programming than that book does.

Many thanks @440bx. Еxcellent.

BTW. What you think about "Let's Build a Compiler!" by Jack W. Crenshaw?

[440bx]

Many thanks @440bx. Еxcellent.

BTW. What you think about "Let's Build a Compiler!" by Jack W. Crenshaw?

You're welcome.

About Jack Crenshaw's "Let's build a compiler", I've mostly scanned through it.  I want to give him credit, he deserves it but, compared to Brinch Hansen's on Pascal Compilers, there is so much missing.  What makes Brinch Hansen's superlative is that he managed to seamlessly integrate the compiler construction concepts while walking (as Crenshaw does) the reader through building a compiler. 

Brinch Hansen and Niklaus Wirth may very well be the best examples that the product of genuine brilliance is simplicity.  The same kind of mind.

While the book is about building a compiler, an attentive reader will realize that the concepts and methodology apply to _any_ program, without exception.  Depending on your initial level of knowledge you may need to read it more than once until it all clicks but, once it does you'll think about writing programs, all programs not just a compiler, very differently.  It will markedly change the way you program.

You won't get that from Crenshaw's "book".  Too much missing but, you will end up with an idea of how to build a compiler.  He deserves credit for that.  I don't want to belittle his work in any way, it's just that Brinch Hansen is in a class by himself.

One of the things you'll learn from that book is that a well written program is self-checking, which means, it won't be as fast as it could be because that self-checking code costs clock cycles but, it will be correct (and systematically testable).  After the program is proven to be correct and _maintainable_ then, and only then, one can entertain the thought of making it faster and, that should be only if it isn't fast enough already - on today's machines if a program is slow is most likely it's because it's poorly designed (which implies poorly coded too.)

HTH.

[ASBzone]

To learn Pascal, I always recommend "oh Pascal" from Doug Cooper, an excellent book, superb programming advice.

I was privileged to get this book when I was first learning Pascal.  It is awesome.

[440bx]

I was privileged to get this book when I was first learning Pascal.  It is awesome.

As you know, I fully share your opinion. 

[PascalDragon]

By the way, it is strange that FPC does not inlining the "High" call, but inlining the "Length" call. By the code below, the Length function is even longer:

Code: Pascal  [Select][+][-]

1. function fpc_dynarray_length(p : pointer) : tdynarrayindex;[Public,Alias:'FPC_DYNARRAY_LENGTH']; compilerproc;
2.   begin
3.      if assigned(p) then
4.        fpc_dynarray_length:=pdynarray(p-sizeof(tdynarray))^.high+1
5.      else
6.        fpc_dynarray_length:=0;
7.   end;
8.  
9.  
10. function fpc_dynarray_high(p : pointer) : tdynarrayindex;[Public,Alias:'FPC_DYNARRAY_HIGH']; compilerproc;
11.   begin
12.      if assigned(p) then
13.        fpc_dynarray_high:=pdynarray(p-sizeof(tdynarray))^.high
14.      else
15.        fpc_dynarray_high:=-1;
16.   end;

Because the compiler is not using FPC_DYNARRAY_LENGTH, it directly generates the code to retrieve the length. And both functions are not marked as inline. One could of course test whether it would help to add inline to fpc_dynarray_high...

[Kays]

[…]

Code: Pascal  [Select][+][-]

1. for x in Data do

Yeah, no, this is no option. You can't assign values to the iterator variable.
What you could do, is having an array of pointers (in Pascal terms, for example: class).