Rein Halbersma wrote:wgarvin wrote:Why not just keep a giant stack of moves per thread, and within each search function just remember pointers to the beginning and end of the current "move list" for that node? That way, you don't ever spend any time allocating or copying movelists, and you don't waste any space. About the only down-side is that you lose control over which cachelines (or cache ways) the movelist for a particular node lies in, but I dont think anybody is optimizing the placement with that much care anyway.
I know you're a fan of STL, but this might be a case where plain simple C style is simpler and faster...
About Big Global Move Stacks: been there done that, didn't like the T-shirt
I currently use the std::array approach with a hopefully sufficient amount of moves. How much ELO does 12% cost anyway? BTW, I'm looking for good custom allocators to see how far one can push the std::vector abstraction penalty. For 5% I'd be willing to switch.
There's actually two std::vector abstraction penalties.
One of them is the performance cost. The other one is the cost that people reading the code need to understand how std::vector works in order to read it.
Of course for std::vector and other bog-standard stuff, this penalty is very small (and worth it, because they add a lot of value over plain C stuff). But there's lots of programmers out there who would claim to know C++ but actually aren't that familiar with most of whats offered by the STL. If I'm being honest, I'm one of them. My opinion is that almost nothing from STL is worth using except for std::vector, std::sort and std::stable_sort, std::unique, std::lower_bound, and maybe std::string and std::map for non-critical things. Everything else is either too complicated or slow (other container classes), is harder to use than the C version (iostream) or lets you write 1 line of code instead of a simple 3-line idiom (std::swap, std::find, etc.)
Its true there are things in <algorithm> which are very handy, if you happen to be in the exact situation they were designed for and if you happen to know what they do. But even if you find them and use them, it just means the next person to read your code will have to look them up too. I would much rather read a simple 3-line loop where I can figure out what it does without having to google it or dig around in some include directory for the header file to find out what "std::find_if" means (and then forget 2 days later, since I only come across it about once a year). I don't think things like std::min_element add any value unless you're using them in some indirect way like passing them as a functor arg to something else.
For the last 9 years I've worked at places that did not use much STL, so most of <algorithm> I've never seen used before in production code. So I'm at one end of that spectrum. But even at the other end... have you ever seen a use of std::next_permutation or std::make_heap or std::random_shuffle? Are there really applications for this stuff, or did the STL designers just add everything they could think of?
[Edit: std::min_element is a good example, because it replaces a loop that remembers a pointer to the element with the lowest value. And you can call it like a function, e.g. in the middle of an argument list for something else. So thats convenient. It might occasionally be useful, but what do you do when you discover that you actually need the *two* lowest values? Or the lowest and the highest? The simplest thing is to just rip out that nice "abstract" call to std::min_element and put the dumb loop back in. At which point, you might (rightly) wonder why you didn't just write the dumb loop in the first place. Of course, some people in this situation immediately set out to write their own min_2_elements template function that returns a std::pair<T, T> or something. They will put it in some utils.h file thats included by everything in your entire project, and proceed to use it in the one or maybe two places where it applies, and there it will sit for the next 6 years without ever being used again. If you find one of your programmers doing this, my advice is to fire them and be more careful when hiring their replacement.]