Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
The Watermelon schreef: > On 3/18/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: >> On 3/17/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: >>> Actually C has it's own fast, small and efficient bitfield >>> specifications... >>> That should be by far the most optimized way to implement a >>> bitfield, since it >>> is done on compiler level. >> I don't know. C bitfields have too many details left >> implementation-defined for my liking. Also I do not like how they >> appear to be normal variables, but cannot be accessed properly as such >> (eg cannot pass it by reference). More importantly, it and Freeciv's >> implementation do not do the same thing. C bitfields are structs, the >> Freeciv bitfields are fixed size arrays wrapped in structs. The >> important difference is that in the latter case, you do not have to >> name each item. >> >> For example, I do not see how we could replace the pTile->tileVisBits, >> which represents one bit of visibility for each player, with the C >> bitfield stuff. You will want to access the bits by index, not by >> name. >> >> Anyway, for our purposes, perhaps we could just as well use a bunch of >> bools. The code is not limited by the PSX's memory constraints >> anymore. As you can see in their own commented out code, this is what >> they did for tileVisBits originally: >> >> // BOOLtileVisible[MAX_PLAYERS]; // Which >> players can see the tile? >> >> - Per > I think either freeciv's array(using a few enum as both 'name' and array > index to access bits I guess) or the old commented-out BOOL one is better > than the current cryptic bitfield. I agree, and must add to that, that just like Per I don't like the C-style bitfields. Yes they could fill the same role as an enum used to index into an array but that still leaves us with the problem that you can't have pointers to a bitfield or its members. Then as for indexed access (such as tile visibility per player) I think we should just use arrays of bools for that. Then whether it should be fixed size or not (i.e. dynamically allocated) is really another issue, but I'd prefer the dynamic variant. > Also we should consider eliminating the > weird << 12 and >> 12,I think they multiply some int values by 4096(<< > 12),then divided it by 4096(>> 12) later to do something that should be > handled by float(like the pie matrix stuff)... I think that bitshifting code is mostly used for the purpose of memory saving? If so we should simply split those values into separate variables. If it's just meant as multiplication / division then replacing it with * 4096 and / 4096 respectively, should do the trick (the compiler optimizes this anyway, most compilers even with optimization turned off). -- Giel signature.asc Description: OpenPGP digital signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/18/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: On 3/17/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > Actually C has it's own fast, small and efficient bitfield specifications... > That should be by far the most optimized way to implement a bitfield, since it > is done on compiler level. I don't know. C bitfields have too many details left implementation-defined for my liking. Also I do not like how they appear to be normal variables, but cannot be accessed properly as such (eg cannot pass it by reference). More importantly, it and Freeciv's implementation do not do the same thing. C bitfields are structs, the Freeciv bitfields are fixed size arrays wrapped in structs. The important difference is that in the latter case, you do not have to name each item. For example, I do not see how we could replace the pTile->tileVisBits, which represents one bit of visibility for each player, with the C bitfield stuff. You will want to access the bits by index, not by name. Anyway, for our purposes, perhaps we could just as well use a bunch of bools. The code is not limited by the PSX's memory constraints anymore. As you can see in their own commented out code, this is what they did for tileVisBits originally: // BOOLtileVisible[MAX_PLAYERS]; // Which players can see the tile? - Per I think either freeciv's array(using a few enum as both 'name' and array index to access bits I guess) or the old commented-out BOOL one is better than the current cryptic bitfield.Also we should consider eliminating the weird << 12 and >> 12,I think they multiply some int values by 4096(<< 12),then divided it by 4096(>> 12) later to do something that should be handled by float(like the pie matrix stuff)... ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/17/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: Actually C has it's own fast, small and efficient bitfield specifications... That should be by far the most optimized way to implement a bitfield, since it is done on compiler level. I don't know. C bitfields have too many details left implementation-defined for my liking. Also I do not like how they appear to be normal variables, but cannot be accessed properly as such (eg cannot pass it by reference). More importantly, it and Freeciv's implementation do not do the same thing. C bitfields are structs, the Freeciv bitfields are fixed size arrays wrapped in structs. The important difference is that in the latter case, you do not have to name each item. For example, I do not see how we could replace the pTile->tileVisBits, which represents one bit of visibility for each player, with the C bitfield stuff. You will want to access the bits by index, not by name. Anyway, for our purposes, perhaps we could just as well use a bunch of bools. The code is not limited by the PSX's memory constraints anymore. As you can see in their own commented out code, this is what they did for tileVisBits originally: // BOOLtileVisible[MAX_PLAYERS]; // Which players can see the tile? - Per ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Samstag, 17. März 2007 schrieb Per Inge Mathisen: > On 3/17/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > > > No, the stuff that works on the psTile->texture UWORD. It contains > > > which tile type, tile flags, and a two-bit rotate value, all > > > compressed together. That stuff should be split apart. > > > > Well, if it's about flags, then a bitfield could be used... > > I want to import the fast, small and efficient bitfield code from > Freeciv to represent the flags, and split out the rotate value and > terrain type value as separate variables. Actually C has it's own fast, small and efficient bitfield specifications... That should be by far the most optimized way to implement a bitfield, since it is done on compiler level. If you don't know what I mean: http://publications.gbdirect.co.uk/c_book/chapter6/bitfields.html --Dennis pgpyu8d1e5dvX.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/17/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > No, the stuff that works on the psTile->texture UWORD. It contains > which tile type, tile flags, and a two-bit rotate value, all > compressed together. That stuff should be split apart. Well, if it's about flags, then a bitfield could be used... I want to import the fast, small and efficient bitfield code from Freeciv to represent the flags, and split out the rotate value and terrain type value as separate variables. You can see the Freeciv "bv" code here: http://svn.gna.org/viewcvs/freeciv/trunk/utility/shared.h?rev=11697&view=markup - Per ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Samstag, 17. März 2007 schrieb Per Inge Mathisen: > On 3/14/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > > > Although you could just store both world and tile coordinates and > > > avoid the bitshifts, they are of course actually used for > > > multiplication and division in this case. > > > > I read about something like that in Gems4, maybe it is what you mean: > > Store the tile coordinate and a more precise coordinate as an offset into > > that tile. > > My idea was rather that you just store a world coordinate for each > tile instead of calculating it anew each time you need it. > > > > Now, the other TILE_* macros and definitions, on the other hand, > > > really could really use larger structs instead of compressing lots of > > > data by bitshifting. > > > > You mean stuff like this? > > #define TILE_OCCUPIED(x)(x->tileInfoBits & BITS_OCCUPIED) > > #define TILE_HAS_STRUCTURE(x) (x->tileInfoBits & BITS_STRUCTURE) > > #define TILE_HAS_FEATURE(x) (x->tileInfoBits & BITS_FEATURE) > > No, the stuff that works on the psTile->texture UWORD. It contains > which tile type, tile flags, and a two-bit rotate value, all > compressed together. That stuff should be split apart. Well, if it's about flags, then a bitfield could be used... pgpqNo7Qs8QxT.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/14/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > Although you could just store both world and tile coordinates and > avoid the bitshifts, they are of course actually used for > multiplication and division in this case. I read about something like that in Gems4, maybe it is what you mean: Store the tile coordinate and a more precise coordinate as an offset into that tile. My idea was rather that you just store a world coordinate for each tile instead of calculating it anew each time you need it. > Now, the other TILE_* macros and definitions, on the other hand, > really could really use larger structs instead of compressing lots of > data by bitshifting. You mean stuff like this? #define TILE_OCCUPIED(x)(x->tileInfoBits & BITS_OCCUPIED) #define TILE_HAS_STRUCTURE(x) (x->tileInfoBits & BITS_STRUCTURE) #define TILE_HAS_FEATURE(x) (x->tileInfoBits & BITS_FEATURE) No, the stuff that works on the psTile->texture UWORD. It contains which tile type, tile flags, and a two-bit rotate value, all compressed together. That stuff should be split apart. - Per ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Donnerstag, 15. März 2007 schrieb The Watermelon: > On 3/15/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > > Well, we are talking about 2 things here. > > 1. The original nonsense I wrote this mail for was that >> is equivalent > > to / > > when operating on POT values. So >> could be replaced with the more > > intuitive /. > > 2. There was the idea to store world and tile coordinates seperately. (At > > least that's what I understood.) As this is also mentioned in Gems4, I > > gave > > the above example. > > 1.you can change it to /,though it'll be hard to know whether that has a > performance hit or not,since every performance killer function is > overshadowed by the renderer(which takes 1-10x times(depends on your gfx > card's gpu and memory speed,I think that might also explains why wz runs > poorly on some radeon cards with weak gpu) more cpu time than all other > stuff sum up) atm... As you followed the discussion, you will know that we are at them moment pretty sure that it has no impact at all. (If you didn't read it yet, you should have a look at my initial mail and the thread with Giel's posting.) pgp1JYOuF3HHZ.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/15/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: Well, we are talking about 2 things here. 1. The original nonsense I wrote this mail for was that >> is equivalent to / when operating on POT values. So >> could be replaced with the more intuitive /. 2. There was the idea to store world and tile coordinates seperately. (At least that's what I understood.) As this is also mentioned in Gems4, I gave the above example. 1.you can change it to /,though it'll be hard to know whether that has a performance hit or not,since every performance killer function is overshadowed by the renderer(which takes 1-10x times(depends on your gfx card's gpu and memory speed,I think that might also explains why wz runs poorly on some radeon cards with weak gpu) more cpu time than all other stuff sum up) atm... 2.not sure if storing both will be beneficial or not,think you need updating both every frame if you do so. ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Donnerstag, 15. März 2007 schrieb The Watermelon: > On 3/14/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: > > Am Mittwoch, 14. März 2007 schrieb Per Inge Mathisen: > > > On 3/14/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: > > > > These are not bitshifts instead of multiplication or division by a > > > > power of two, but actually bitshifts to conserve the precious memory > > > > of the PSX. The correct solution is to expand the relevant structures > > > > a bit, so that we do not have to compress the data by bitshifting. > > > > I've wanted to do this for a long time, but I never got around to it. > > > > > > Actually, I was thinking of something else when I wrote this. I > > > realized this when I saw your commit. > > > > > > Although you could just store both world and tile coordinates and > > > avoid the bitshifts, they are of course actually used for > > > multiplication and division in this case. > > > > I read about something like that in Gems4, maybe it is what you mean: > > Store the tile coordinate and a more precise coordinate as an offset into > > that > > tile. Chapter 2.4, ~~Precisionproblems of large world coordinates~~ > > > > So you would get something like this (copied from the above mentioned > > book): > > struct droid{ > >Vector2s tileCoord; > >Vector3f offsetCoord; > >... > > }; > > > > Vector3f getWorldCoord(tileCoord, offsetCoord) > > { > >return tileCoord * tileSize + offsetCoord; > > } > > > > union Vector2s{ > >struct { > >Uint16 x, y; > >}; > >Uint32 xy; > > }; > > (He made it a union for easier initialization and comparison. Mostly > > added it > > here, because I didn't know about anonymous structs before. Possibly > > handy in > > some situations.) > > > > > Now, the other TILE_* macros and definitions, on the other hand, > > > really could really use larger structs instead of compressing lots of > > > data by bitshifting. > > > > You mean stuff like this? > > #define TILE_OCCUPIED(x)(x->tileInfoBits & BITS_OCCUPIED) > > #define TILE_HAS_STRUCTURE(x) (x->tileInfoBits & BITS_STRUCTURE) > > #define TILE_HAS_FEATURE(x) (x->tileInfoBits & BITS_FEATURE) > > > > Even though it is not extremely ugly, it could be done using a bitset, I > > agree. I guess it wouldn't even harm performance or memory size. > > > > -Dennis > > it wont work,because you cant do *(multiply) and +(plus) on vector struct > in wz... That was just so everyone gets the rought idea what the article suggests... > I think wz does need the coords to be shifted left and right when doing > world coords to tile coords 'translation' unless you change all relevant > parts... Well, we are talking about 2 things here. 1. The original nonsense I wrote this mail for was that >> is equivalent to / when operating on POT values. So >> could be replaced with the more intuitive /. 2. There was the idea to store world and tile coordinates seperately. (At least that's what I understood.) As this is also mentioned in Gems4, I gave the above example. > for example,the building in wz uses tile coords instead of world coords > iirc,the building must be at least 1 tile big and the multi-tile buildings > use the top-left tile of all tiles it 'hogs' as tile coords,so when you > test something's collision against a building's,you need to change the tile > coords to world coords via that sometileX,Y <<< TILE_SHIFT. > > offset will be useless too,because wz updates units before updating > tiles,basically it appends the mobile's x,y velocity to its world coords > then do some funky world-to-tile shifts to know whether that mobile object > has moved out its current tile/moved in a new tile in current loop iirc. > > I think the solutions you describe works optimal in a game/app with a > floating point world coord system,but doesnt work very well for wz's > integer power of 2 world coords... --Dennis pgpilAElg76W9.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/14/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: Am Mittwoch, 14. März 2007 schrieb Per Inge Mathisen: > On 3/14/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: > > These are not bitshifts instead of multiplication or division by a > > power of two, but actually bitshifts to conserve the precious memory > > of the PSX. The correct solution is to expand the relevant structures > > a bit, so that we do not have to compress the data by bitshifting. > > I've wanted to do this for a long time, but I never got around to it. > > Actually, I was thinking of something else when I wrote this. I > realized this when I saw your commit. > > Although you could just store both world and tile coordinates and > avoid the bitshifts, they are of course actually used for > multiplication and division in this case. I read about something like that in Gems4, maybe it is what you mean: Store the tile coordinate and a more precise coordinate as an offset into that tile. Chapter 2.4, ~~Precisionproblems of large world coordinates~~ So you would get something like this (copied from the above mentioned book): struct droid{ Vector2s tileCoord; Vector3f offsetCoord; ... }; Vector3f getWorldCoord(tileCoord, offsetCoord) { return tileCoord * tileSize + offsetCoord; } union Vector2s{ struct { Uint16 x, y; }; Uint32 xy; }; (He made it a union for easier initialization and comparison. Mostly added it here, because I didn't know about anonymous structs before. Possibly handy in some situations.) > Now, the other TILE_* macros and definitions, on the other hand, > really could really use larger structs instead of compressing lots of > data by bitshifting. You mean stuff like this? #define TILE_OCCUPIED(x)(x->tileInfoBits & BITS_OCCUPIED) #define TILE_HAS_STRUCTURE(x) (x->tileInfoBits & BITS_STRUCTURE) #define TILE_HAS_FEATURE(x) (x->tileInfoBits & BITS_FEATURE) Even though it is not extremely ugly, it could be done using a bitset, I agree. I guess it wouldn't even harm performance or memory size. -Dennis it wont work,because you cant do *(multiply) and +(plus) on vector struct in wz... I think wz does need the coords to be shifted left and right when doing world coords to tile coords 'translation' unless you change all relevant parts... for example,the building in wz uses tile coords instead of world coords iirc,the building must be at least 1 tile big and the multi-tile buildings use the top-left tile of all tiles it 'hogs' as tile coords,so when you test something's collision against a building's,you need to change the tile coords to world coords via that sometileX,Y <<< TILE_SHIFT. offset will be useless too,because wz updates units before updating tiles,basically it appends the mobile's x,y velocity to its world coords then do some funky world-to-tile shifts to know whether that mobile object has moved out its current tile/moved in a new tile in current loop iirc. I think the solutions you describe works optimal in a game/app with a floating point world coord system,but doesnt work very well for wz's integer power of 2 world coords... ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Mittwoch, 14. März 2007 schrieb Per Inge Mathisen: > On 3/14/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: > > These are not bitshifts instead of multiplication or division by a > > power of two, but actually bitshifts to conserve the precious memory > > of the PSX. The correct solution is to expand the relevant structures > > a bit, so that we do not have to compress the data by bitshifting. > > I've wanted to do this for a long time, but I never got around to it. > > Actually, I was thinking of something else when I wrote this. I > realized this when I saw your commit. > > Although you could just store both world and tile coordinates and > avoid the bitshifts, they are of course actually used for > multiplication and division in this case. I read about something like that in Gems4, maybe it is what you mean: Store the tile coordinate and a more precise coordinate as an offset into that tile. Chapter 2.4, ~~Precisionproblems of large world coordinates~~ So you would get something like this (copied from the above mentioned book): struct droid{ Vector2s tileCoord; Vector3f offsetCoord; ... }; Vector3f getWorldCoord(tileCoord, offsetCoord) { return tileCoord * tileSize + offsetCoord; } union Vector2s{ struct { Uint16 x, y; }; Uint32 xy; }; (He made it a union for easier initialization and comparison. Mostly added it here, because I didn't know about anonymous structs before. Possibly handy in some situations.) > Now, the other TILE_* macros and definitions, on the other hand, > really could really use larger structs instead of compressing lots of > data by bitshifting. You mean stuff like this? #define TILE_OCCUPIED(x)(x->tileInfoBits & BITS_OCCUPIED) #define TILE_HAS_STRUCTURE(x) (x->tileInfoBits & BITS_STRUCTURE) #define TILE_HAS_FEATURE(x) (x->tileInfoBits & BITS_FEATURE) Even though it is not extremely ugly, it could be done using a bitset, I agree. I guess it wouldn't even harm performance or memory size. -Dennis pgpostbVADVVF.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/14/07, Per Inge Mathisen <[EMAIL PROTECTED]> wrote: These are not bitshifts instead of multiplication or division by a power of two, but actually bitshifts to conserve the precious memory of the PSX. The correct solution is to expand the relevant structures a bit, so that we do not have to compress the data by bitshifting. I've wanted to do this for a long time, but I never got around to it. Actually, I was thinking of something else when I wrote this. I realized this when I saw your commit. Although you could just store both world and tile coordinates and avoid the bitshifts, they are of course actually used for multiplication and division in this case. Now, the other TILE_* macros and definitions, on the other hand, really could really use larger structs instead of compressing lots of data by bitshifting. - Per ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
On 3/14/07, Dennis Schridde <[EMAIL PROTECTED]> wrote: "We" are using (x >> TILE_SHIFT) in a lot of places in the code. A (very) quick micro-benchmark resulted in timings similar to these: 0m2.790s 0m2.800s These are not bitshifts instead of multiplication or division by a power of two, but actually bitshifts to conserve the precious memory of the PSX. The correct solution is to expand the relevant structures a bit, so that we do not have to compress the data by bitshifting. I've wanted to do this for a long time, but I never got around to it. - Per ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Am Mittwoch, 14. März 2007 schrieb Giel van Schijndel: > Dennis Schridde schreef: > > Hello! > > > > "We" are using (x >> TILE_SHIFT) in a lot of places in the code. > > > > A (very) quick micro-benchmark resulted in timings similar to these: > > 0m2.790s > > 0m2.800s > > > > These timings are flawed (too short time), but before I thought about > > this I investigated... > > The experts in ##c also told me that the compiler would optimize (x / > > 2^n) into (x >> n) anyway. (Which later timings proved, after I extended > > the time to ~1m.) > > > > So even if the shift should not harm, it still makes the code cryptic and > > should be exchanged in my opinion. > > > > Other opinions? > > Well, I agree completely with you that bit shifting should (almost; > there are always exceptions but I don't consider this one of them) never > be used instead of dividing/multiplying only because it is a speed > optimization. However I wouldn't have gone as far as benchmarking I > would just let the compiler dump its compiled assembly into a file > rather than assemble it into an object file. Hehe... That's what I've been told in ##c, too. I just don't know any assembly, so I couldn't do it properly. > For example this source code: > > int i = 72; > > i /= 8; > > results in this assembly instruction (a lot more really but those are > > just moving the value into CPU registers from memory etc.): > > sarl$3, %eax > > Which in C would be equivalent to this (SARL = Shift Arithmetic Right Long) > > > i >>= 3; > > This is with optimizations disabled (-O0). > > There is however one difference in the generated assembly code between > an explicit bitshift or a division when operating on a _signed_ integer. > When dividing a signed integer the compiler adds about 5 instructions to > check whether the sign bit is set and if so deals with the situation. > This make sure the integer remains negative if not divided by a negative > number and to ensure the sign bit doesn't take on any numerical value. > When using the optimizer (-O1 or higher) however I can't see any > difference at all between `i >>= 3` and `i /= 8`. > > My point; priority one: make code readable. And only when the optimizer > does a bad job (and only if it is at a critical point in the code; e.g. > a nested loop) write optimized code but DO comment heavily on your code > if you do optimize. In this specific example the bitshift is not even an optimization... As I've been told in ##c and you said above: (x / 2^n) produces the same code as (x >> n). So what stays is the crypticness of the bitshift without any benefit at all. But I guess we agree anyway. --Dennis pgpWP9v9SeNwR.pgp Description: PGP signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev
Re: [Warzone-dev] x >> TILE_SHIFT vs. x / TILE_UNITS
Dennis Schridde schreef: > Hello! > > "We" are using (x >> TILE_SHIFT) in a lot of places in the code. > > A (very) quick micro-benchmark resulted in timings similar to these: > 0m2.790s > 0m2.800s > > These timings are flawed (too short time), but before I thought about this I > investigated... > The experts in ##c also told me that the compiler would optimize (x / 2^n) > into (x >> n) anyway. (Which later timings proved, after I extended the time > to ~1m.) > > So even if the shift should not harm, it still makes the code cryptic and > should be exchanged in my opinion. > > Other opinions? Well, I agree completely with you that bit shifting should (almost; there are always exceptions but I don't consider this one of them) never be used instead of dividing/multiplying only because it is a speed optimization. However I wouldn't have gone as far as benchmarking I would just let the compiler dump its compiled assembly into a file rather than assemble it into an object file. For example this source code: > int i = 72; > i /= 8; results in this assembly instruction (a lot more really but those are just moving the value into CPU registers from memory etc.): > sarl$3, %eax Which in C would be equivalent to this (SARL = Shift Arithmetic Right Long) > i >>= 3; This is with optimizations disabled (-O0). There is however one difference in the generated assembly code between an explicit bitshift or a division when operating on a _signed_ integer. When dividing a signed integer the compiler adds about 5 instructions to check whether the sign bit is set and if so deals with the situation. This make sure the integer remains negative if not divided by a negative number and to ensure the sign bit doesn't take on any numerical value. When using the optimizer (-O1 or higher) however I can't see any difference at all between `i >>= 3` and `i /= 8`. My point; priority one: make code readable. And only when the optimizer does a bad job (and only if it is at a critical point in the code; e.g. a nested loop) write optimized code but DO comment heavily on your code if you do optimize. -- Giel signature.asc Description: OpenPGP digital signature ___ Warzone-dev mailing list Warzone-dev@gna.org https://mail.gna.org/listinfo/warzone-dev