Compare struct speed vs array - is it a fair way to compare?

[Ivan]

I think I have to evolve my old programming style in Basic and had a go at Struct. So far it seems that the old array is faster or I don't use struct correctly?

REM compare struct speed vs array - is it a fair way to compare?

MODE 22
OFF

dim_size = 999
colours = 15
ajust_x = 100
ajust_y = 100
ajust_z = 1000

DIM object{name$(dim_size),pos{x(dim_size),y(dim_size),z(dim_size),c(dim_size)}}
XT=TIME
FOR t% = 0 TO dim_size
object.name$(t%) = CHR$(RND(25)+65)
object.pos.x(t%) = FN_rnd_num(ajust_x)
object.pos.y(t%) = FN_rnd_num(ajust_y)
object.pos.z(t%) = FN_rnd_num(ajust_z)
object.pos.c(t%) = FN_rnd_num(colours)
GCOL(object.pos.c(t%))
MOVE object.pos.x(t%),object.pos.y(t%)
DRAW object.pos.z(t%),object.pos.y(t%)
PRINT TAB(1,1);object.name$(t%)",";object.pos.x(t%);",";object.pos.y(t%);",";object.pos.z(t%);" "
NEXT t%
timer1 = TIME-XT
PRINT TAB(1,2);timer1

DIM name$(dim_size),x(dim_size),y(dim_size),z(dim_size),c(dim_size)
YT=TIME
FOR t% = 0 TO dim_size
name$(t%) = CHR$(RND(25)+65)
x(t%) = FN_rnd_num(ajust_x)
y(t%) = FN_rnd_num(ajust_y)
z(t%) = FN_rnd_num(ajust_z)
c(t%) = FN_rnd_num(colours)
GCOL c(t%)
MOVE x(t%),y(t%)
DRAW z(t%),y(t%)
PRINT TAB(1,4)name$(t%);",";x(t%);",";y(t%);",";z(t%);" "
NEXT t%
timer2 = TIME-YT
PRINT TAB(1,5);timer2

PRINT TAB(1,7);"Timer difference: "timer1 - timer2

ON
END


DEF FN_rnd_num(size)
= RND(dim_size)+size

[KenDown]

The difference in speed isn't all that great, so unless your application needs every last clock cycle of speed, I wouldn't worry about it.

Last year I rewrote a database program that I wrote many moons ago and decided, just for fun, to use a structure for the various fields. I have never programmed using structures before - couldn't quite see the point - but I was impressed at just how much easier it was to write the database and have it debugged, up and running. That, I think, is the point of structures: they may be fractionally slower in execution, but in writing the program they are faster and easier.

[RichardRussell]

So far it seems that the old array is faster or I don't use struct correctly?

It is not surprising that an array is faster - the interpreter has less work to do - but one shouldn't be deciding on whether to use an array or a structure on the basis of speed. Indeed I would expect that, in general, coding techniques which lead to a program being easier to understand and easier to maintain also tend to make it slower, whereas programs written with speed as the primary consideration tend to be quite unreadable.

As always there are exceptions to the general rule. In one of David Williams's shoot-em-up video games (Forces of Darkness I think) using structures actually improved performance. This was because of the efficiency of passing an object to a function or procedure. If everything about the object (position, orientation, velocity, state, sprite pointer etc.) can be held in a structure - typically an element of a structure array - then being able to pass it as a single parameter saves time. Using arrays would have meant passing multiple parameters.

Fortunately, with the performance of modern CPUs and PCs, it is relatively unusual for raw speed to be an important factor. Unless I know up-front that the program I am writing will be speed-critical, and most aren't, I design my code with clarity, maintainability and reliability at the forefront. That won't always mean using structures rather than arrays, clearly arrays are more suitable for some things (not least if array arithmetic or whole-array operations are of value), but I will if they are the right choice.

[RichardRussell]

Here's an (over-) simplified example of when using structures can offer an advantage. I am assuming a set of 100000 objects, each of which can be represented by 7 attributes (a name, 5 numeric parameters and a pointer). The program iterates over each object, passing it to a procedure which updates its parameters. When I run it here the array version takes over twice as long as the structure version!

Clearly this is not typical, the example is contrived and normally arrays are faster than structures, but it does illustrate that one should be careful not to make assumptions.

Code: Select all

      HIMEM = PAGE + 10000000

      REM Structure method:
      DIM object{(100000) n$, x, y, a, u, v, s%%}
      TIME = 0
      FOR I% = 0 TO DIM(object{()},1)
        PROCobj1(object{(I%)})
      NEXT
      PRINT "Time using structure array = "; TIME

      CLEAR

      REM Array method:
      DIM n$(100000), x(100000), y(100000), a(100000), u(100000), v(100000), s%%(100000)
      TIME = 0
      FOR I% = 0 TO DIM(n$(),1)
        PROCobj2(n$(I%), x(I%), y(I%), a(I%), u(I%), v(I%), s%%(I%))
      NEXT
      PRINT "Time using separate arrays = "; TIME

      END

      DEF PROCobj1(o{})
      o.x += o.u : o.y += o.v
      ENDPROC

      DEF PROCobj2(n$, RETURN x, RETURN y, a, u, v, s%%)
      x += u : y += v
      ENDPROC

[hellomike]

Yes, very obvious speed difference. Nice example Richard!
What puzzles me however is why array version speed increases by almost 30% when I REM out the very first line?

Thanks

Mike

[RichardRussell]

What puzzles me however is why array version speed increases by almost 30% when I REM out the very first line?

REMming out the first line results in a 'DIM space' error here, in both BB4W and BBCSDL (that's why the statement is there!). The only way to run it successfully without that line is first to run it with that line to raise HIMEM (and that only works in BB4W).

But if you do contrive to run it without the first line, make sure you are comparing like with like by ensuring that the total program length is exactly the same in the two cases you are comparing. Otherwise you may be seeing a data-alignment effect entirely unrelated to the actual change in the code. As I expect you know, the x86 CPU will access aligned data more quickly than non-aligned data, so simply adding one byte to a program (perhaps by adding a single letter to a REM statement) can change the speed.

[hellomike]

You are absolutely correct Richard. I forgot that raising HIMEM is for the entire IDE session and not every time for the program that is about to run. My apologies.
And you are also correct that when adding one single character after a REM there is the same speed increase. So in addition this also is a pretty solid example of how (mis)alignment can cause delays.

Regards,

Mike

[Ivan]

Richard: Thanks - my example is correct or?

I had never seen DIM used in a for loop:

FOR I% = 0 TO DIM(n$(),1)

Can you clarify how above works in an educational way?

[RichardRussell]

I forgot that raising HIMEM is for the entire IDE session.

Arguably, yet another advantage of running the BASIC program in a separate process, as both BBCSDL IDEs do, since it's always starting 'with a clean slate'.

And you are also correct that when adding one single character after a REM there is the same speed increase.

In a more typical program these effects are likely to average out, with a speed increase in one place probably being balanced by a speed decrease in another. So unless you are very unlucky, the overall effect of alignment is likely to be minimal. But it's particularly in small programs (of exactly the sort which tend to be used as benchmarks!), with one tight loop dominating the execution time, that the effect can be quite large. As I always say, beware benchmarks because they can be misleading.

[DDRM]

Hi Ivan,

DIM() can be used as a function, to return (in this case) the size of one dimension of an array: try

Code: Select all

      DIM s$(5,4)
      PRINT DIM(s$(),1)
      PRINT DIM(s$(),2)

Since in BBC BASIC when you dimension an array so size n you get elements from 0 to n, the code you posted would loop through each element of n$() (for example, allowing you to set or test it). The advantage is that you can use the same code for any sized array.

Best wishes,

D