[OT] Money for nothing, and your bit flips for free?

Steve smorrey at gmail.com
Wed Feb 7 16:13:29 MST 2007


Ok so I watched s carefully and found out that the bitwise compliment
operator I was using was not infact flipping any bits.  It effectively
did nothing.  The string coming in from a flip was the same string
coming out :(

Turns out I had to create an assignment to get it function as I wanted.

s[y] = ~s[y];

I also isolated it into a new function called flip that took a
std::string and returned the flipped std::string

This brought things more into line with expectations, in that we no
longer had lots of "free flips".

In fact in the end I came up with an average ratio of 2 clock cycles
per flip.  But at least it worked.

Still I wanted to see if I could do it better, the assignments
inherent in calling the function passing it a string, flipping the
bits, and returning the new flipped string, then copying it into the
original variable seemed a little excessive.

So what I did in the end was create a function called flip.  flip
takes a std::string refference, and manipulates the bits directly.

This is what the results are showing now (I modified the program to
show a little more debugging output when I figured out it wasn't
actually doing what I expected)

g++ -O3 flip.cpp
./a.out "Hello World" 1000000
New String is: Hߨ
And back once more is: Hello World
Started: 0
Ended: 110000
Performed 1000000 bit flips on a 11 byte string in 110000 cycles

Whatever clock is measuring, this program is now doing it in what
feels like a reasonable amount of them :) a ratio of roughly 1 tick to
10 flips

For those interested here is the new flip.cpp

#include <iostream>
#include <time.h>

inline void flip(std::string& s){
	int y = 0;
	while(y++ < s.length()){
		s[y] = ~s[y];
	}
}
int main(int agc, char *argv[]){
	int x = 0,y = 0, count = atoi(argv[2]);
	std::string s = argv[1];
	//std::cout << "String is : " << s << std::endl;
	clock_t start = clock();
	while(x++ < count){
		flip(s);
	}
	clock_t end = clock();
	std::cout << "New String is : " << s << std::endl;
	flip(s);
	std::cout << "And back once more is: " << s << std::endl;
	std::cout << "Started: " << start << "\nEnded: " << end
	<< "\nPerformed "<< count << " bit flips on a " << s.length()
	<< " byte string in " << difftime(end,start) << " cycles\n"
	<< "ratio is " << (end / count) << std::endl;
	
	return(0);
}

Any addtional feedback is greatly appreciated!

Regards,
On 2/7/07, Nicholas Leippe <nick at leippe.com> wrote:
> clock() returns a clock_t, which isn't a unix timestamp (seconds) nor
> necessarily one tick per cpu clock cycle.
>
> difftime() expects a time_t, which is a unix timestamp.  There's no guarantee
> that it will compute the correct difference for two clock_t values (which can
> suffer from wraparound).
>
> Even if it were one tick per cpu clock cycle, remember also that the ipc of
> some instructions often exceeds 1 on modern cpus.  With loop unrolling on a
> good optimizing compiler targeting an OO cpu with multiple pipelines, several
> operations can sometimes be combined further increasing the effective ipc.
>
>
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */
>


More information about the PLUG mailing list