Sudoku Py / C++11 / D?

[Chris Cain]

On Thursday, 16 August 2012 at 23:13:56 UTC, maarten van damme 
wrote:
> great, going to play around with it tomorrow.
> Caching the possibilities is going to look really ugly but 
> you're
> right, it's going to give quiet a boost in performance.
>
> I'm also going to format your source code a bit more and see if 
> I can
> follow it's logic as it seems to be way more efficient. 
> (although
> compilation is failing here, I'm running dmd 2.059 and it gives 
> "can't
> stride on chunks!(short))
>
> would using short or bytes increase performance compared to 
> integers?
> if so, why did you use shorts instead of bytes?

Gonna chime in a bit here:

There's a lot of factors at play when deciding to use shorts vs 
bytes vs native-sized ints. The best way to decide is to time all 
of them and see which works best overall.

With caching on a larger problem, I'd guess that the smaller you 
go, the better. The reason is that you run the risk of your data 
getting large enough that it can't all fit in the L2 cache and 
waiting for information to come from memory takes forever 
(comparatively speaking).

Also, I just looked at your solution (not Mr. Gehr's solution), 
but it looks like you could approach this much more efficiently.

It seems like you're storing a lot of information in arrays of 
ints. At least some of that could be stored in a bitmap/bitset 
(http://en.wikipedia.org/wiki/Bit_array) and give you 
significantly better memory efficiency. Array!bool in 
std.container will actually do the correct thing and store things 
like a bitset, so you don't necessarily have to implement your 
own (however, I think that it stores it in an int when you could 
use a short to hold 1-9 ... but it's not enough to really worry 
about).