Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

OK, I've been playing with D for a while (and been in love with its expressive power and simplicity, to be honest). However, since I'm still new to D, I'm facing a few issues.

Let's take the following example. All the following program does is to take numbers in the 0..10000000 (fairly big one, for benchmarking purposes) and for each one of them return a vector/array with the positions of bits set (in binary).

E.g.

4 = 100(2) => [ 2 ]
5 = 101(2) => [ 0, 2 ]
6 = 110(2) => [ 1, 2 ]
7 = 111(2) => [ 0, 1, 2]

And so on...

Now here's my C++ code (no vector reserve etc being used) :

// bits.cpp

#include <vector>
#include <iostream>
#include "math.h"

using namespace std;

vector<unsigned int> bitsSet(unsigned long long bitboard)
{
    unsigned int n;
    vector<unsigned int> res;

    for (n = 0; bitboard != 0; n++, bitboard &= (bitboard - 1))
    {
        res.push_back(log2(bitboard & ~(bitboard-1)));
    }

    return res;
}

int main()
{
    for (int k=0; k<10000000; k++)
    {
        vector<unsigned int> res = bitsSet(k);
    }

    return 0;
}

And here's my D code :

// bits.d

import std.stdio;
import std.math;

int[] bitsSet(ulong bitboard)
{
    int[] res;

    for (int n=0; bitboard!=0; n++, bitboard&=(bitboard-1))
        res ~= cast(int)log2(bitboard & ~(bitboard-1));

    return res;
}

void main(string[] args)
{
    for (ulong k=0; k<10000000; k++)
    {
        int[] bits = bitsSet(k);
    }
}

Now, given that the 2 pieces of code are compiled with g++ bits.cpp -o cbits (or clang++ bits.cpp -o cbits) and dmd bits.d -ofdbits, respectively, these are my benchmark results, using time (on Mac OS X 10.8.2) :

For C++ :

time ./cbits

real    0m19.742s
user    0m19.722s
sys 0m0.012s

For D :

time ./dbits

real    0m14.914s
user    0m14.891s
sys 0m0.017s

This looks OK. (with D being - for me - noticeably faster).

NOTE :

Now, if I try to use something like res.reserve(64); in my C++ bitsSet function, though, time drops to around 7s.... which IS significantly faster. Tried something like res.length = 64; (in my D code), time dropped to around 11s (though slower than C++), but I'm not sure if the result is the same...


What further optimizations would you suggest for my D code, so that it's at least as fast as my C++ code?


Results with Compiler Optimization flags :

With clang++ bits.cpp -O3 -o cbits

time ./cbits

real    0m8.994s
user    0m8.986s
sys 0m0.006s

With dmd bits.d -O -release -inline -m64 -ofdbits

time ./bitsd

real    0m14.083s
user    0m14.034s
sys 0m0.014s

Which looks pretty amazing (or bizarre). Clang managed to go from 19 to 8 seconds, while D optimization did nothing???

EDIT : So, is there no hope that my D code will run as fast as it's C++ counterpart?

share|improve this question
3  
What further optimisations? What about... -O3? –  R. Martinho Fernandes Feb 6 '13 at 8:34
3  
I could suggest compiling with optimizations on (-O2 or -Os) for the C++ code. –  Matthieu M. Feb 6 '13 at 8:34
8  
@Dr.Kameleon optimisations in the code are a pointless exercise if you request of the compiler to make a slow program. –  R. Martinho Fernandes Feb 6 '13 at 8:36
3  
I would be more than happy to know why this question has received 3 downvotes and 2 close votes. I'm really curious... (I know D may sound obscure to most people, but that's definitely not a reason to downvote... without any explanation)... –  Dr.Kameleon Feb 6 '13 at 8:40
1  
If you're looking for ways to improve the D code, a better place is codereview IMO. If you're asking to compare the results, it's not really constructive. –  Luchian Grigore Feb 6 '13 at 8:46
show 19 more comments

migrated from stackoverflow.com Feb 6 '13 at 12:13

This question came from our site for professional and enthusiast programmers.

1 Answer

up vote 8 down vote accepted

How about: using res.length = 64; and then in your loop replace

res ~= cast(int)log2(bitboard & ~(bitboard-1));

by:

res[n] = cast(int)log2(bitboard & ~(bitboard-1));

But to be honest this type of code will be completely dominated by allocations, which is not entirely interesting as a language benchmark. Try to reuse the same array instead.

And there is much faster ways of locating bits (see core.bitop).

tl;dr you're optimizing a slow program.

share|improve this answer
    
Thanks for the suggestions, I'm currently looking into it. (Actually I've tried what you suggest with res.length but without any great difference). One question : I knew about std.intrinsic. However, I'm a bit perplexed : Is it working with ulongs (64-bit unsigned ints)? (this has to be able to work with 64-bit ints, otherwise it's not of much use to me...) –  Dr.Kameleon Feb 6 '13 at 9:27
    
"you're optimizing a slow program" - Better than optimizing a fast one, isn't it? No, really +1 ;) –  Christian Rau Feb 6 '13 at 9:36
    
@ponce Just trying to figure out what's going on : is std.intrinsic still supported? (dmd and ldmd2 both give me errors, and I definitely cannot find the std/intrinsic.d file in D's current release. (Perhaps it's been deprecated since D v1.0?) –  Dr.Kameleon Feb 6 '13 at 9:39
    
My bad, std.intrinsic is now called core.bitop. bsf makes you avoid a call to log2. –  ponce Feb 6 '13 at 10:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.