Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

Faster, no (unknown) problems

Faster, problematic

Same speed, no (unknown) problems

Same speed, problematic

Slower, no other (unknown) problems

Slower, problematic

Doesn't work at all

[Veroule]

For those that are interested MSVC was optomizing the x*dimy*4 etc in the 'big if' of graphicst::display.

Here is the pertinent assembly:

Spoiler (click to show/hide)

0066679A  |. 8B87 98030000  ||MOV EAX,DWORD PTR DS:[EDI+398]
006667A0  |. 8B4F 24        ||MOV ECX,DWORD PTR DS:[EDI+24]
006667A3  |. 0FAFC3         ||IMUL EAX,EBX
006667A6  |. 894424 24      ||MOV DWORD PTR SS:[ESP+24],EAX
006667AA  |. 03C6           ||ADD EAX,ESI
006667AC  |. 03C0           ||ADD EAX,EAX
006667AE  |. 03C0           ||ADD EAX,EAX
006667B0  |. 8A1401         ||MOV DL,BYTE PTR DS:[ECX+EAX]
006667B3  |. 03C8           ||ADD ECX,EAX
006667B5  |. 894C24 1C      ||MOV DWORD PTR SS:[ESP+1C],ECX
006667B9  |. 8B0D 682B3301  ||MOV ECX,DWORD PTR DS:[1332B68]
006667BF  |. 885424 0F      ||MOV BYTE PTR SS:[ESP+F],DL
006667C3  |. 3A1408         ||CMP DL,BYTE PTR DS:[EAX+ECX]
006667C6  |. 0F85 B4000000  ||JNZ dwarfort.00666880
006667CC  |. 8B5424 1C      ||MOV EDX,DWORD PTR SS:[ESP+1C]
006667D0  |. 8A52 01        ||MOV DL,BYTE PTR DS:[EDX+1]
006667D3  |. 3A5408 01      ||CMP DL,BYTE PTR DS:[EAX+ECX+1]
006667D7  |. 0F85 A3000000  ||JNZ dwarfort.00666880
006667DD  |. 8B5424 1C      ||MOV EDX,DWORD PTR SS:[ESP+1C]
006667E1  |. 8A52 02        ||MOV DL,BYTE PTR DS:[EDX+2]
006667E4  |. 3A5408 02      ||CMP DL,BYTE PTR DS:[EAX+ECX+2]
006667E8  |. 0F85 92000000  ||JNZ dwarfort.00666880
006667EE  |. 8B5424 1C      ||MOV EDX,DWORD PTR SS:[ESP+1C]
006667F2  |. 8A52 03        ||MOV DL,BYTE PTR DS:[EDX+3]
006667F5  |. 3A5408 03      ||CMP DL,BYTE PTR DS:[EAX+ECX+3]
006667F9  |. 0F85 81000000  ||JNZ dwarfort.00666880

for this c code:

Spoiler (click to show/hide)

if (screen[x2*dimy*4 + y2*4 + 0] == screen_old[x2*dimy*4 + y2*4 + 0] &&
          screen[x2*dimy*4 + y2*4 + 1] == screen_old[x2*dimy*4 + y2*4 + 1] &&
          screen[x2*dimy*4 + y2*4 + 2] == screen_old[x2*dimy*4 + y2*4 + 2] &&
          screen[x2*dimy*4 + y2*4 + 3] == screen_old[x2*dimy*4 + y2*4 + 3]

For things like that particular if I am a big fan of a union.
typedef union {
 uint_8 array[4];
 uint_32 Value;
} screen_union;

After adjusting all the references then we can make the if
if (screen[x2*dimy*4 + y2*4].Value == screen_old[x2*dimy*4 + y2*4].Value
 && the other tests)

The same can be done with an unint_32* cast.  The pointer cast makes for a much more surgical change but has slightly lower readability to the union method.  I would definitely suggest a pointer cast in this case as it is a good speed gain.  The speed gain comes from both being able to reduces those 4 CMP instructions to one and being able to calculate the address outside of the loops and just increment the address with each loop.  The assembly above shows the calculation and is inside the 2 for loops.

There is a reason we wanted bigger processors.  I already want a 256 bit processor with 128 registers.

[bombcar]

I'd rather have a 64 bit processor with 512 registers, even if some are 128 bits wide.

[Veroule]

You could also eliminate nearly all the multiplications in that section of the code by changing your array strategy from 2 dimensional to contiguous.  In order to make this change replace the calculations in addchar.

Spoiler (click to show/hide)

void addchar(unsigned char c,char advance=1)
                {
                  if(screenx>=clipx[0]&&screenx<=clipx[1]&&
                     screeny>=clipy[0]&&screeny<=clipy[1])
                    {
                      screen[screenx*dimy*4 + screeny*4 + 0]=c;
                      screen[screenx*dimy*4 + screeny*4 + 1]=screenf;
                      screen[screenx*dimy*4 + screeny*4 + 2]=screenb;
                      screen[screenx*dimy*4 + screeny*4 + 3]=screenbright;
                     
                      screentexpos[screenx*dimy + screeny]=0;
                    }
                  if(advance)screenx++;
                }

with

Spoiler (click to show/hide)

void addchar(unsigned char c,char advance=1)
                {
                  if(screenx>=clipx[0]&&screenx<=clipx[1]&&
                     screeny>=clipy[0]&&screeny<=clipy[1])
                    {
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 0]=c;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 1]=screenf;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 2]=screenb;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 3]=screenbright;
                     
                      screentexpos[screenx*init.display.grid_y + screeny]=0;
                    }
                  if(advance)screenx++;
                }

and move that function back into graphics.cpp.  There is also the other function that handles setting screentexpos and related variables; same treatment there.

Then display looks something like this
uint_32* s=(uint_32*)screen;
uint_32* so=(uint_32*)screen_old;
for (uint_32 pos=init.display.grid_y*init.display.grid_y-1;pos;pos--) {
 if (s[pos]!=so[pos] && etc) etc
}

[Andir]

Sorry, I know I should probably study that code a bit more, but from glancing at what's going on it looks like someone is trying to make a singular dimensional vector to apply to a multidimensional problem...

What's wrong with a multidimensional vector?  The object overhead?  How big is this object we are talking about here?  Screen resolution?

[PencilinHand]

Sorry, I know I should probably study that code a bit more, but from glancing at what's going on it looks like someone is trying to make a singular dimensional vector to apply to a multidimensional problem...

What's wrong with a multidimensional vector?  The object overhead?  How big is this object we are talking about here?  Screen resolution?

You could also eliminate nearly all the multiplications in that section of the code by changing your array strategy from 2 dimensional to contiguous.

Spoiler (click to show/hide)

  In order to make this change replace the calculations in addchar.
[spoiler]void addchar(unsigned char c,char advance=1)
                {
                  if(screenx>=clipx[0]&&screenx<=clipx[1]&&
                     screeny>=clipy[0]&&screeny<=clipy[1])
                    {
                      screen[screenx*dimy*4 + screeny*4 + 0]=c;
                      screen[screenx*dimy*4 + screeny*4 + 1]=screenf;
                      screen[screenx*dimy*4 + screeny*4 + 2]=screenb;
                      screen[screenx*dimy*4 + screeny*4 + 3]=screenbright;
                     
                      screentexpos[screenx*dimy + screeny]=0;
                    }
                  if(advance)screenx++;
                }
with
void addchar(unsigned char c,char advance=1)
                {
                  if(screenx>=clipx[0]&&screenx<=clipx[1]&&
                     screeny>=clipy[0]&&screeny<=clipy[1])
                    {
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 0]=c;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 1]=screenf;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 2]=screenb;
                      screen[screenx*init.display.grid_y*4 + screeny*4 + 3]=screenbright;
                     
                      screentexpos[screenx*init.display.grid_y + screeny]=0;
                    }
                  if(advance)screenx++;
                }and move that function back into graphics.cpp.  There is also the other function that handles setting screentexpos and related variables; same treatment there.

Then display looks something like this
uint_32* s=(uint_32*)screen;
uint_32* so=(uint_32*)screen_old;
for (uint_32 pos=init.display.grid_y*init.display.grid_y-1;pos;pos--) {
 if (s[pos]!=so[pos] && etc) etc
}

If I recall correctly, most CPU's can perform 3 add operations in the same time as one multiplication operation.

[Aachen]

Please pardon the interruption.

When exporting after world-generation, rather than a world-map image, I get repeated screenshots of the world-gen final screen strung together. I'm not sure if it's worth the time to upload an image file for review (and hopefully this hasn't already been discussed to death). I've had the same result with the three worlds I've created in the current version.

[Andir]

You could also eliminate nearly all the multiplications in that section of the code by changing your array strategy from 2 dimensional to contiguous.

I see no 2 dimensional arrays anywhere (but I haven't looked at the git code...) All I see in these quotes is two contiguous arrays with two different implementations...

screen[x2*dimy*4 + y2*4 + 0]
turned to:
screen[screenx*dimy*4 + screeny*4 + 0]=c;

...or am I missing a conjoined set of brackets "[ x ][ y ]" or something in these quotes somewhere?

[PencilinHand]

You could also eliminate nearly all the multiplications in that section of the code by changing your array strategy from 2 dimensional to contiguous.

I see no 2 dimensional arrays anywhere (but I haven't looked at the git code...) All I see in these quotes is two contiguous arrays with two different implementations...

screen[x2*dimy*4 + y2*4 + 0]
turned to:
screen[screenx*dimy*4 + screeny*4 + 0]=c;

...or am I missing a conjoined set of brackets "[ x ][ y ]" or something in these quotes somewhere?

I believe that is the point.  Veroule was suggesting a code change to avoid using 2 dimensional arrays which eliminates the need for multiplication in a performance critical section of code.

------

Please pardon the interruption.

When exporting after world-generation, rather than a world-map image, I get repeated screenshots of the world-gen final screen strung together. I'm not sure if it's worth the time to upload an image file for review (and hopefully this hasn't already been discussed to death). I've had the same result with the three worlds I've created in the current version.

It is a known bug which Toady will have to handle.  Baughn,they guy doing the graphics code, can't touch the code responsible for image export.
"- Image export is generally broken; some don't work, some actually freeze the game. Don't try it."

[Andir]

That doesn't make sense... there's no need for multiplication with an array of arrays because it's simply a memory pointer.  The current contiguous method requires multiplication to find the proper address space to fiddle with.

[PencilinHand]

That doesn't make sense... there's no need for multiplication with an array of arrays because it's simply a memory pointer.  The current contiguous method requires multiplication to find the proper address space to fiddle with.

I think if we both looked at the .git code then Veroule's suggestion would make more sense.  Otherwise, you will have to wait for someone more competent....

[Andir]

Excellent point... stupid lazy me sticking my nose where it doesn't belong.  I should be in bed anyway.

[Baughn]

Incrementing the pointers instead of recalculating the offset for each tile makes perfect sense, it's just that the arrays didn't use to be contiguous; until quite recently they were always 256x256, never mind the actual grid size.

Well, there we go then. Fixed.

[vyznev]

That doesn't make sense... there's no need for multiplication with an array of arrays because it's simply a memory pointer.  The current contiguous method requires multiplication to find the proper address space to fiddle with.

While I think it would probably be best to let this subthread die out (or continue it elsewhere), I'd just like to quickly note that it's usually faster to do a multiplication to index a contiguous 2D array than to fetch a pointer from memory for a ragged array.

Of course, this assumes that the multiplier is either constant or already stored in a register, or at least in on-chip cache, and that the pointer isn't.  Since there's only one multiplier, but one pointer for each row, this is likely at least for random access patterns.  Still, YMMV, especially if you're traversing the array row by row.  Also, for the sake of completeness, I should note that things can be very different if you're writing code for a very old or very low-end CPU that lacks a fast multiplier -- but if you're coding for such platforms, there are specific optimization tricks you'll be using anyway, and in any case there's no hope of DF ever running on such systems.

[CobaltKobold]

and in any case there's no hope of DF ever running on such systems.

I...have hope...

How old would "such systems" need to be, anyway?

[vyznev]

Older than the mid-90s or so, I'd say.  The Amiga 500 and 1200 computers that I learned to code on had slow multiplication (around 40 cycles for the MC68000 CPU in the A500, ~28 for the newer A1200 with its 68020 processor) and small clock multipliers (effectively 1x for fast RAM, 2x for chip RAM), making memory access comparatively fast.  Atari ST and old Apple Macintosh computers used the same Motorola 680x0 series processors.  (The 68060, introduced in 1994, had very fast multiplication, but did not see much desktop use.)  On the PC side, Intel x86 CPUs up to the 486 were quite similar.

During the middle 90s, several things happened at roughly the same time: multipliers got faster, superscalar architecture was introduced to mainstream desktop CPUs, and RAM speeds started lagging behind CPU speeds, necessitating higher clock multipliers.  Put together, these mean that a modern desktop CPU may (under ideal circumstances) be able to do one multiplication every cycle (the latency will be higher, but still only a few cycles) while needing several cycles to fetch data from memory.