Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
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
Replies are listed 'Best First'.
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:


        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 (Canon) 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 choroba (Canon) 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 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 chilling in the Monastery: (5)
As of 2015-07-30 04:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls