C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Two speed related questions          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message pd42 Guest Posted: Thu Oct 21, 2004 5:12 pm    Post subject: Two speed related questions Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Tokyo Tomy Guest Posted: Fri Oct 22, 2004 5:40 pm    Post subject: Re: Two speed related questions [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Quote: Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). There were arguments that C style array should have a boundary check mechanism, because you could easily violate the boundary. K&R rejected the arguments, saying that if the array had the mechanism, you could not remove it easily, when you did not need it, and if you needed the mechanism, you could easily add it by yourself. Nowadays many people argue that the vector is better than C style array, because the vector is safer than C style array against the boundary violation. If you don't need the frequent boundary checks and run time expansion of size, C style array is much better than the vector for performance in speed and in memory usage. But you also have to pay attention to maintenance of your codes and I think the vector is better for maintenance. A compromise is that you limit the usage of C style array to critical portions for speed. 2) I have the choice of using 1-dim arrays rather that 2-dim arrays Quote: (with some additional work to calculate the 1-dim array index), is this worthwhile trying? I don't think one dimension C style array as a two dimension array has a difference in speed from two dimension array, if you think about optimizer. Two dimension array is better for maintenance. Speed comparison by measurement is necessary for a complier you use, when you need more speed. Quote: Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Oct 22, 2004 5:44 pm    Post subject: Re: Two speed related questions [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Quote: Speed is criticial to my chess program. Speed will depend a lot on which compiler and which library implementation you use. Quote: 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). It depends on what you are doing. If you need the dynamic scaling capacity, it's far from sure that you could do better than std::vector. For the representation of a chessboard, however, I'd definitly use something like signed char[8][8] -- the size of the chessboard certainly isn't going to change during the execution of the program, and at least to date, no implementations of std::vector quite achieve the speed of a built-in array. (Although there too, a lot depends on what you are doing. In many cases, there is very, very little difference in the speed of indexation. On the otherhand, allocating a structure which contains a char[8][8] will almost certainly be significantly faster than allocating one which contains an std::vector< std::vector<> >, with all vectors scaled to 8.) Quote: 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? That depends largely on the machine. Note too that on some (many?) machines, indexing into an array of char (signed char, unsigned char) will be faster than indexing into an array of any other type. Quote: Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. The problem is that even if someone else has done the comparison, their results are really only valid for their compiler and their machine. There are some valid generalizations: the construction of something like class Position { // .... signed char board[ 8 ][ 8 ] ; } ; will almost surely run significantly faster than the constructor for class Position { std::vector< std::vector< signed char > > board ; Position() : board( 8, std::vector< signed char >( 8 ) ) ... } ; for example. But for the most part, a lot will depend on your compiler and your machine. If multiplication is expensive, using an array of pointers to simulate two dimensions may be faster -- if indirection is expensive, the straightforeward solution may be faster. On many machines, keeping the size of elements in an array a power of 2 can make things faster; indexing into an array of char types is often faster than indexing into an array of other types. (On Intel, I think that there are actually several "optimized" sizes: 1, 2, 4 or 8.) A lot depends on just how far you are willing to go for speed. Often, using several separate arrays of basic types like char, int, double, etc., will be faster than having a single array of struct/class. But that's a heavy price to pay in readability and maintainability for what is probably a very small speed gain. -- James Kanze GABI Software http://www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top rishi Guest Posted: Sun Oct 24, 2004 4:10 am    Post subject: Re: Two speed related questions Hi, The speed issues in std::vector as compared to native 'c' style arrays are probably because of reallocation issues of std::vector. However, if you know the size of an array then using std::vector::reserve and then pushing elements into it can offset the cost of reallocation. Another, hitch in std::vector usage could be the non-garuntee that the standard imposes on the implementers of std::vector about cost of copy being equivalent to memmove,memcpy functions whereever they are applicable. In applications where construction happens only once and all other operation on the array is just access of elements it might be worthwhile not to invest time on saving the small time excess that std::vector has over native c arrays. The standard interface and the generality of std::vector are not properties easily disposed off for small time gains. Rishi Nair [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Quote: Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Tue Oct 26, 2004 4:16 am    Post subject: Re: Two speed related questions [email]hosoda (AT) jtec (DOT) or.jp[/email] (Tokyo Tomy) wrote in message news:<49c1da0b.0410211823.22e55ea6 (AT) posting (DOT) google.com>... Quote: pd42 (AT) hotmail (DOT) com (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). There were arguments that C style array should have a boundary check mechanism, because you could easily violate the boundary. K&R rejected the arguments, saying that if the array had the mechanism, you could not remove it easily, when you did not need it, and if you needed the mechanism, you could easily add it by yourself. That was probably true in the seventies, when C was being developed. I rather doubt that it is true today -- Ada seems to use bounds checking with no problems, for example. The "obvious" solution would be to do bounds checking with [], and have a member function along the lines of "unsafeGetAt" for the rare occasions where you couldn't afford it. Of course, when C was being developped, there weren't member functions, and arrays weren't classes, so that option wasn't available. Quote: Nowadays many people argue that the vector is better than C style array, because the vector is safer than C style array against the boundary violation. I've never heard that argument. Because, of course, it is false. Boundary violations are undefined behavior in both cases. The main argument against the built-in arrays is that they aren't first class types. An array behaves differently from other types in very many cases. Quote: If you don't need the frequent boundary checks and run time expansion of size, C style array is much better than the vector for performance in speed and in memory usage. The benchmarks I've seen show no measurable difference in access times. I've not seen too many other benchmarks, but I would guess that in most cases, C style arrays will be cheaper to allocate, e.g. an operation like "new C" will be faster if new contains C-style arrays rather than std::vector. Quote: But you also have to pay attention to maintenance of your codes and I think the vector is better for maintenance. A compromise is that you limit the usage of C style array to critical portions for speed. 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? I don't think one dimension C style array as a two dimension array has a difference in speed from two dimension array, if you think about optimizer. That's only true if you are iterating over the elements in a fixed order. Even after optimization, if i and j are parameters to a function, the code for something like "x[i][j]" will be different depending on whether x is defined as char [8][8] or as char*[8]. Which of the two will be faster will depend on the hardware. Quote: Two dimension array is better for maintenance. Speed comparison by measurement is necessary for a complier you use, when you need more speed. A two dimensional (C-style) array is the equivalent of a one dimensional array with the index calculated using a multiplication. The alternative, if the structure has two dimensions, is a one dimensional array of char*. -- James Kanze GABI Software http://www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michiel Salters Guest Posted: Wed Oct 27, 2004 1:05 am    Post subject: Re: Two speed related questions [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Quote: Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. A chess program is one of the very rare examples in which the fixed size array makes sense. It is a very critical datastructure; it has been 8x8 for several centuries and 8 happens to be ideal for bitshifts. You don't need to use a 1-D array; because you always know the exact sizes. The optimizer will notice the arithmetic that happens behind the scenes, and because the array bounds are constants, it can easily optimize that. The troublesome questions are whether you use a class field {...}[8][8] or a class board { field1[8][8]; field2[8][8]; } - this can make a very big difference. You might actually have more than one type; for some algorithms you need more data per field than for others (e.g. for some algorithms you might need to keep track of what pieces could reach that field, which means you need 32 bits - again, it seems chess was made for computers) HTH, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Tokyo Tomy Guest Posted: Wed Oct 27, 2004 2:23 pm    Post subject: Re: Two speed related questions [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote in message news:<d6652001.0410250108.3b30b658 (AT) posting (DOT) google.com>... Quote: hosoda (AT) jtec (DOT) or.jp (Tokyo Tomy) wrote in message news:<49c1da0b.0410211823.22e55ea6 (AT) posting (DOT) google.com>... [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). There were arguments that C style array should have a boundary check mechanism, because you could easily violate the boundary. K&R rejected the arguments, saying that if the array had the mechanism, you could not remove it easily, when you did not need it, and if you needed the mechanism, you could easily add it by yourself. That was probably true in the seventies, when C was being developed. I rather doubt that it is true today -- Ada seems to use bounds checking with no problems, for example. The "obvious" solution would be to do bounds checking with [], and have a member function along the lines of "unsafeGetAt" for the rare occasions where you couldn't afford it. Of course, when C was being developped, there weren't member functions, and arrays weren't classes, so that option wasn't available. Nowadays many people argue that the vector is better than C style array, because the vector is safer than C style array against the boundary violation. I've never heard that argument. Because, of course, it is false. Boundary violations are undefined behavior in both cases. ... Thank you for correcting me for my misunderstanding that I have held for a long time. I admit that std::vector has no boundary check. Then, I wander what are good things for std::vector. Resize ability is one of them, but this is not good for OP who request a fixed size array. Std::vector is as safe as C style array. Is this right? If the boundary check is no more problem in the modern programming technology as Kaze said, why does not the boundary check based on the technology is applied for std::vector to make it safer. Quote: 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? I don't think one dimension C style array as a two dimension array has a difference in speed from two dimension array, if you think about optimizer. That's only true if you are iterating over the elements in a fixed order. Even after optimization, if i and j are parameters to a function, the code for something like "x[i][j]" will be different depending on whether x is defined as char [8][8] or as char*[8]. Which of the two will be faster will depend on the hardware. Two dimension array is better for maintenance. Speed comparison by measurement is necessary for a complier you use, when you need more speed. A two dimensional (C-style) array is the equivalent of a one dimensional array with the index calculated using a multiplication. The alternative, if the structure has two dimensions, is a one dimensional array of char*. I thought about the following case. (1) int array_2d[10][10]; array_2d[9][3] = 20; // all pointer arithmetic (2) int index; int array_1d[100]; index = 9 + 3; // index arithmetic array_1d[index] = 20; // pointer arithmetic The pointer arithmetic for array_1d looks simpler than that of arry_2d, but the second case(2) requires the index arithmetic. I thought compilers would produce optimized codes for the both cases, and the resulted codes had little difference in efficiency. Do you think that the speed difference between the two cases above depend on hardware? If so, please explain what difference in hardware makes the difference. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Gerhard Menzl Guest Posted: Fri Oct 29, 2004 2:05 am    Post subject: Re: Two speed related questions Tokyo Tomy wrote: Quote: Thank you for correcting me for my misunderstanding that I have held for a long time. I admit that std::vector has no boundary check. Then, I wander what are good things for std::vector. Resize ability is one of them, but this is not good for OP who request a fixed size array. Allow me to correct another misunderstanding: std::vector *does* have boundary checks; it's just that you have the choice whether you want to make use of them. operator[] does not check; if you pass an invalid index, you get undefined behaviour. Passing an invalid index to at(), however, throws an out_of_range exception. -- Gerhard Menzl #dogma int main () Humans may reply by replacing the obviously faked part of my e-mail address with "kapsch". [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Oct 29, 2004 2:06 am    Post subject: Re: Two speed related questions [email]hosoda (AT) jtec (DOT) or.jp[/email] (Tokyo Tomy) wrote in message news:<49c1da0b.0410262152.5f4e5df8 (AT) posting (DOT) google.com>... Quote: kanze (AT) gabi-soft (DOT) fr wrote in message news:<d6652001.0410250108.3b30b658 (AT) posting (DOT) google.com>... I've never heard that argument. Because, of course, it is false. Boundary violations are undefined behavior in both cases. ... Thank you for correcting me for my misunderstanding that I have held for a long time. I admit that std::vector has no boundary check. Then, I wander what are good things for std::vector. It is a real type. It behaves like every other type. It does not convert to a pointer at the drop of a hat. When you pass it to a function, you can use pass by value, or pass by reference -- in both cases, the called function can determine the actual size. Quote: Resize ability is one of them, but this is not good for OP who request a fixed size array. Std::vector is as safe as C style array. Is this right? It's safer in the sense that it carries its size along with it, and client code can always ask. Quote: If the boundary check is no more problem in the modern programming technology as Kaze said, why does not the boundary check based on the technology is applied for std::vector to make it safer. Boundary checking is typically not a problem when it is built into the language, and the language is designed with it in mind -- the compiler knows the semantics, and even the intent, behind the comparisons, and can often eliminate them. Boundary checks implemented in a class like vector can also be detected and eliminated, but it is considerably more difficult for the compiler (unless the compiler has built-in knowledge of the semantics of std::vector.) Still, IMHO, it was a design error not to require boundary checks in operator[], and have a second function, say unsafe_at, without them in the STL. Still, the behavior is undefined, and there are STL implementations which check. Quote: 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? I don't think one dimension C style array as a two dimension array has a difference in speed from two dimension array, if you think about optimizer. That's only true if you are iterating over the elements in a fixed order. Even after optimization, if i and j are parameters to a function, the code for something like "x[i][j]" will be different depending on whether x is defined as char [8][8] or as char*[8]. Which of the two will be faster will depend on the hardware. Two dimension array is better for maintenance. Speed comparison by measurement is necessary for a complier you use, when you need more speed. A two dimensional (C-style) array is the equivalent of a one dimensional array with the index calculated using a multiplication. The alternative, if the structure has two dimensions, is a one dimensional array of char*. I thought about the following case. (1) int array_2d[10][10]; array_2d[9][3] = 20; // all pointer arithmetic (2) int index; int array_1d[100]; index = 9 + 3; // index arithmetic You mean 9*10 + 3, if you want the same effect as the one dimension array. Quote: array_1d[index] = 20; // pointer arithmetic The pointer arithmetic for array_1d looks simpler than that of arry_2d, but the second case(2) requires the index arithmetic. I thought compilers would produce optimized codes for the both cases, and the resulted codes had little difference in efficiency. I expect that most compilers will generate exactly the same code for the two. (My experience has been that occasionnally, compilers do a better job when they do the optimizing. Which would result in better code for (1). But such cases are rare, and the difference is normally very slight.) That's basically what I meant when I said that a C style two dimensional array is really the equivalent of a one dimensional array. Quote: Do you think that the speed difference between the two cases above depend on hardware? If so, please explain what difference in hardware makes the difference. Even with the above, there are probably compilers which will use two index/offset registers for (1), but calculate the index separately and use a single index/offset register for (2) -- this might result in one less machine instruction for (1). But a compiler which doesn't recognize the equivalence of the two expressions when optimizing is turned on, and generate whichever code is optimal, is pretty primitive. The big difference can occur if instead of int array[10][10], I declare int *array[10], then initialize each element with a pointer to 10 ints. For an expression like array[i][j], in the first case, the compiler will generate something like the equivalent of &array + (i*10+j)*sizeof(int), and in the second, *(&array+(i*sizeof(int*))+i*sizeof(int). The size of int and int* is usually a power of two, and can be implemented as a simple shift -- on an IA-32 architecture, there are addressing modes in which the multiplication doesn't have to be done at all. In the first variant, however, there is also a multiplication by 10. In the second, there is an additional memory access. On some architectures, multiplication will be a lot more expensive than a memory access, on others, it will be significantly cheaper. (I've worked on both -- in one case, multiplication 40 times more expensive than a memory access, and in aother, about 4-8 times less expensive, depending in which cache the accessed memory was found.) Note that if multiplication is slow, the compiler will normally replace multiplication by a constant with a combination of shifts and adds/subtracts -- on my machine (Sun Sparc), the code generated for 127*h is actually the equivalent of h<<7-h. As a result, the cost of the multiplication will vary according to the dimension of the array -- a dimension which is a power of 2 will result in the fastest code. And if you need an array[10][10], the fastest solution (on my machine) is probably to declare array[16][16], and just use the first 10 elements in each dimension. (Note, however, that this will multiply the memory use by more that 2.5.) -- James Kanze GABI Software http://www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top pd42 Guest Posted: Fri Oct 29, 2004 2:08 am    Post subject: Re: Two speed related questions [email]Michiel.Salters (AT) logicacmg (DOT) com[/email] (Michiel Salters) wrote in message news:<fcaee77e.0410260314.7bb74ee0 (AT) posting (DOT) google.com>... Quote: pd42 (AT) hotmail (DOT) com (pd42) wrote in message news:<c3a8d849.0410200523.7a09c2a1 (AT) posting (DOT) google.com>... Speed is criticial to my chess program. 1) I have the choice of using fixed size arrays rather than STL::vector, is it worthwhile trying? (Of course I would need to do the housekeeping for array length, myself, but this is quite easy to implement). 2) I have the choice of using 1-dim arrays rather that 2-dim arrays (with some additional work to calculate the 1-dim array index), is this worthwhile trying? Reason for asking is that I don't want to redesign my data structures (which is a lot of work) if someone else has compared both approaches already, only to find out that there is no gain. A chess program is one of the very rare examples in which the fixed size array makes sense. It is a very critical datastructure; it has been 8x8 for several centuries and 8 happens to be ideal for bitshifts. You don't need to use a 1-D array; because you always know the exact sizes. The optimizer will notice the arithmetic that happens behind the scenes, and because the array bounds are constants, it can easily optimize that. The troublesome questions are whether you use a class field {...}[8][8] or a class board { field1[8][8]; field2[8][8]; } - this can make a very big difference. You might actually have more than one type; for some algorithms you need more data per field than for others (e.g. for some algorithms you might need to keep track of what pieces could reach that field, which means you need 32 bits - again, it seems chess was made for computers) HTH, Michiel Salters Actually it's not the representation of the chess board that is important in this context (I use 64-bit words to do that, works great), it's the storage of the moves, returned by the movegenerator. The search function is called recursively when going deeper into the game tree. Since the search function has to call the move generator to find all positions that are one level deeper in the game tree, you can imagine that there are many individual move lists on the stack. A single move is represented by a 32-bit integer (of which only 24 bits are used, 8 'spare'). Currently I use the vector class to populate move lists, but my guess is that fixed size int[] arrays would be faster. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Oct 29, 2004 2:35 pm    Post subject: Re: Two speed related questions [email]pd42 (AT) hotmail (DOT) com[/email] (pd42) wrote in message news:<c3a8d849.0410280447.451ad382 (AT) posting (DOT) google.com>... Quote: Actually it's not the representation of the chess board that is important in this context (I use 64-bit words to do that, works great), I'm curious as to how you do that. I would have thought that you needed several different possible values for each square. (When I did a chess program, I basically used the equivalent of signed char[8][8], with 0 for unoccupied, the absolute value for the type of piece, and negative for black, positive for white. But using something like struct { bool isBlack; char piece ; } might be faster on some machines.) Quote: it's the storage of the moves, returned by the movegenerator. The search function is called recursively when going deeper into the game tree. Since the search function has to call the move generator to find all positions that are one level deeper in the game tree, you can imagine that there are many individual move lists on the stack. A single move is represented by a 32-bit integer (of which only 24 bits are used, 8 'spare'). And here, I would have thought twelve bits sufficient (six for the starting position, and six for the ending). Note that optimizing memory does not always mean optimizing speed. In the end, something like struct { int startRow, startCol, endRow, endCol ; } might turn out to be faster. Quote: Currently I use the vector class to populate move lists, but my guess is that fixed size int[] arrays would be faster. Only if you can fix an absolut upper limit on the size (the depth of search). More generally, concerning the representation, you will have to benchmark very carefully to know whether the extra work necessary to extract fields smaller than char from a word is offset by the reduced number of cache misses due to the data structures being smaller. And designing a significant benchmark for this is far from trivial, since the results depend very much on what you are doing with the structures. -- James Kanze GABI Software http://www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.