Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

In-place bitwise NOT?

by BrowserUk (Pope)
on Jul 26, 2013 at 17:27 UTC ( #1046569=perlquestion: print w/ replies, xml ) Need Help??
BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

I need to invert the bits in a (very) large bitstring. Doing so is easy enough:

$bits = ~$bits;

The problem is that involves duplicating the entire bitstring and then copying it.

What I want is $bits ~= ?; but that obviously doesn't exist.

I could xor it with an equal length string of 1s, but same problem.

Can anyone think of a way of doing this whilst avoiding doubling the memory requirement?


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on In-place bitwise NOT?
Select or Download Code
Re: In-place bitwise NOT?
by choroba (Abbot) on Jul 26, 2013 at 17:33 UTC
    Probably not fast enough:
    $bits =~ s/(.)/~$1/ges;
    لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

        Nice. Thank you.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

      No. I'm dealing with multi-gigabyte bitstrings.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
Re: In-place bitwise NOT?
by hdb (Prior) on Jul 26, 2013 at 17:44 UTC

    Create a bitstring class that supports lazy evaluation.

    UPDATE: Loop using substr

    my $blocksize = 1000000; my $lb = length $bin; my $offset = 0; while( $offset < $lb ) { substr $bin, $offset, $blocksize, ~substr( $bin, $offset, $blocksize + ); $offset += $blocksize; }

    Too slow as well?

      Nice! Benchmark of various solutions (I hope I did not spoil it again):

      Output on my machine:

      1..5 ok 1 - double negation ok 2 - single - classic ok 3 - classic - long ok 4 - classic - translate ok 5 - classic - str Rate single translate long classic str single 0.328/s -- -100% -100% -100% -100% translate 161/s 48834% -- -26% -39% -59% long 217/s 66040% 35% -- -18% -45% classic 263/s 80093% 64% 21% -- -33% str 394/s 119839% 145% 81% 50% --
      لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

        Here's my version of that. The first run is on a 1MB string will all tests enabled.

        The second run is on a 1GB string with the classic and s/// solutions disable because life's too short :)

        C:\test>1046579 -N=2**20 1048576 Rate single long classic str translate single 1.72/s -- -99% -100% -100% -100% long 134/s 7707% -- -71% -79% -81% classic 468/s 27047% 248% -- -26% -33% str 632/s 36579% 370% 35% -- -9% translate 695/s 40233% 417% 49% 10% -- C:\test>1046579 -N=2**30 1073741824 (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) s/iter str translate str 1.96 -- -21% translate 1.54 27% --

        The modified code:

        #! perl -slw use strict; use Benchmark qw(cmpthese); sub single { ${ $_[0] } =~ s/(.)/~$1/ges; } sub long { ${ $_[0] } =~ s/(.{1,10000})/~$1/ges; } sub classic { ${ $_[0] } = ~${ $_[0] }; } sub str { my $blocksize = 10000; my $lb = length ${ $_[0] }; my $offset = 0; while( $offset < $lb ) { substr ${ $_[0] }, $offset, $blocksize, ~substr( ${ $_[0] }, $offset, $blocksize ); $offset += $blocksize; } } BEGIN { my $rev = join '', map sprintf( "\\x%02x", $_ ), reverse 0 .. 25 +5; eval "sub translate { \${ \$_[0] } =~ tr[\\x00-\\xff][$rev] } ; 1 +" or die $@; } our $N //= 256; $N = eval "0+$N"; #print $N; our $bits = pack 'C*', 0 .. 255; $bits x= ( $N / 256 ); cmpthese -3, { # classic => q[ classic( \$bits) ], # single => q[ single( \$bits ) ], # long => q[ long( \$bits ) ], translate => q[ translate( \$bits ) ], str => q[ str( \$bits ) ], };

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: In-place bitwise NOT?
by Perlbotics (Abbot) on Jul 26, 2013 at 18:02 UTC

    I am not sure, if this works as you expect... maybe the macros and wrappers generate a copy under the hood?

    use Inline C; use strict; use warnings; my $x = "012\xf0ABC\x0f\x00\x01\xff"; print unpack("H*", $x ), "\n"; # 303132f04142430f0001ff flipbits( $x, length $x ); print unpack("H*", $x ), "\n"; # cfcecd0fbebdbcf0fffe00 __END__ __C__ void flipbits(char* a, int len ) { for ( ; len-- ; ++a ) *a ^= 0xff; }

    Update: Switching to 32bit blocks gave a huge improvement on my 32bit setup...

    void flipbits32(char* a, int len ) { int blocks = len >> 2; if ( sizeof blocks == 4 ) { /* try 32bit blocks */ for ( ; blocks-- ; a += 4 ) *( (unsigned int*) a ) ^= 0xffffffffU +; /* TODO: add treatment for last 1..3 bytes if len is not a multipl +e of 4 */ } else { /* fallback to 8bit */ for ( ; len-- ; ++a ) *a ^= 0xff; } }
    Benchmark:
    Rate str inline inline32 str 69.1/s -- -37% -69% flipbits 110/s 59% -- -51% flipbits32 223/s 222% 103% --

    Potential next steps which are also less general, but that's the price to pay:

      That certainly works and doesn't appear to do any copying. It comes out at nearly 50% faster than tr//:

      C:\test>1046579 -N=2**20 Rate str translate C str 656/s -- -8% -37% translate 713/s 9% -- -32% C 1047/s 60% 47% --

      The only downside is that it imposes the need for a compiler on a module that otherwise doesn't need one.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
Re: In-place bitwise NOT?
by Grimy (Pilgrim) on Jul 27, 2013 at 16:56 UTC
    Nobody proposed a vec solution yet. Here’s one:
    use feature say; $_ = "012\xf0ABC\x0f\x00\x01\xff"; say unpack "H*"; # 303132f04142430f0001ff for (my $i = length; $i--; vec($_, $i, 8) ^= ~0) {} say unpack "H*"; # cfcecd0fbebdbcf0fffe00
    Could probably be optimized for 32/64 bits. Whatever. I'm too lazy to benchmark it.

      That was my first attempt :)

      sub byvec { no warnings 'portable'; vec( ${ $_[0] }, $_, 64 ) ^= ~0 for 0 .. ( length( ${ $_[0] } ) / +8 ); }

      Nowhere close to tr///.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
Re: In-place bitwise NOT?
by snoopy (Deacon) on Jul 27, 2013 at 22:31 UTC
    substr can be used as an lvalue:
    my $bytes = length( $bits ); for (my $offset = 0; $offset < $bytes; $offset += 4096) { my $chunk = 4096; $chunk = $bytes - $offset if $offset + $bytes > $bytes; substr($bits, $offset, $bytes) = ~ substr($bits, $offset, $bytes); }

      Indeed. See hdb's post.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1046569]
Approved by Happy-the-monk
Front-paged by MidLifeXis
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (9)
As of 2014-10-02 18:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (72 votes), past polls