[prev in list] [next in list] [prev in thread] [next in thread] 

List:       perl5-changes
Subject:    [Perl/perl5] bf8741: Create and use single_1bit_pos32()
From:       Karl Williamson via perl5-changes <perl5-changes () perl ! org>
Date:       2021-07-30 11:41:45
Message-ID: Perl/perl5/push/refs/heads/blead/6e7a78-4a1b7b () github ! com
[Download RAW message or body]

  Branch: refs/heads/blead
  Home:   https://github.com/Perl/perl5
  Commit: bf874180e9a7a8fbb74ab7eaa5c683ecc5a6ffc7
      https://github.com/Perl/perl5/commit/bf874180e9a7a8fbb74ab7eaa5c683ecc5a6ffc7
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M embed.fnc
    M embed.h
    M globvar.sym
    M inline.h
    M perl.h
    M proto.h
    M regcomp.c

  Log Message:
  -----------
  Create and use single_1bit_pos32()

This moves the code from regcomp.c to inline.h that calculates the
position of the lone set bit in a U32.  This is in preparation for use
by other call sites.


  Commit: 995a49544ee5d0b46679907f5ba9fe50be890438
      https://github.com/Perl/perl5/commit/995a49544ee5d0b46679907f5ba9fe50be890438
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M embed.fnc
    M embed.h
    M globvar.sym
    M inline.h
    M perl.h
    M proto.h

  Log Message:
  -----------
  Add 64bit single-1bit_pos()

This will prove useful in future commits on platforms that have 64 bit
capability.

The deBruijn sequence used here, taken from the internet, differs
from the 32 bit one in how they treat a word with no set bits.  But this
is considered undefined behavior, so that difference is immaterial.

Apparently figuring this out uses brute force methods, and so I decided
to live with this difference, rather than to expend the time needed to
bring them into sync.


  Commit: 8a6ab0a2b6184deb2f9a99f0a9622e8f836de4bd
      https://github.com/Perl/perl5/commit/8a6ab0a2b6184deb2f9a99f0a9622e8f836de4bd
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Perl_variant_byte_number: Generalize

The current mechanism doesn't work if the lowest bit is the one set.  At
the moment that doesn't matter as we aren't looking at that bit anyway.
But a future commit will refactor things so that bit will be looked at.
So prepare for that.  The new expression is simpler, besides.


  Commit: 58ddb8c5c1121d947ee72818b81ee254edb17699
      https://github.com/Perl/perl5/commit/58ddb8c5c1121d947ee72818b81ee254edb17699
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Perl_variant_byte_number: Move assert()

This should be called only when it is known there is a variant byte.
The assert() previously wasn't checking that precisely


  Commit: 19d2c525bfed3f9eea1099e6eb745dbb50ca818b
      https://github.com/Perl/perl5/commit/19d2c525bfed3f9eea1099e6eb745dbb50ca818b
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M embed.fnc
    M embed.h
    M inline.h
    M proto.h

  Log Message:
  -----------
  Create and use 32 and 64 bit lsbit_pos() fcns

The existing code to determine the position of the least significant 1
bit in a word is extracted from variant_byte_number() and moved to a new
function in preparation for being called from other places.

A U32 version is created, and on 64 bit platforms, a second, parallel,
version taking a U64 argument is also created.  This is because future
commits may care about the word size differences.


  Commit: ad494d15d17ba5d23ba2b9adc3d990c5f566f6f1
      https://github.com/Perl/perl5/commit/ad494d15d17ba5d23ba2b9adc3d990c5f566f6f1
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M regcomp.h

  Log Message:
  -----------
  regcomp.h: Add internal macro

This returns the locale bitmap field from an ANYOF node.

In this commit, it just tidies up the code, omitting lengthy casts.  But
a future commit will use it on its own.


  Commit: b5288edf08d3f057f4cb70d49137c0a10da649a4
      https://github.com/Perl/perl5/commit/b5288edf08d3f057f4cb70d49137c0a10da649a4
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M regexec.c

  Log Message:
  -----------
  regexec.c: Use lsbit_pos32() to avoid iterations

Before this commit, the code looped through a bitmap looking for a set
bit.  Now that we have a fast way to find where a set bit is, use it,
and avoid the fruitless iterations.


  Commit: 330cd0ce7cbde4175b21369c749c6a3186d2ac77
      https://github.com/Perl/perl5/commit/330cd0ce7cbde4175b21369c749c6a3186d2ac77
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M embed.fnc
    M embed.h
    M inline.h
    M proto.h

  Log Message:
  -----------
  Create and use 32 and 64 bit msbit_pos() fcns

The existing code to determine the position of the most significant 1
bit in a word is extracted from variant_byte_number(), and generalized
to use the deBruijn method previously added that works on any bit in the
word, rather than the existing method which looks just at the msb of
each byte.  The code is moved to a new function in preparation for being
called from other places.

A U32 version is created, and on 64 bit platforms, a second, parallel,
version taking a U64 argument is also created.  This is because future
commits may care about the word size differences.


  Commit: fc1bb663cac6846450ceb387751b491f2ecef13e
      https://github.com/Perl/perl5/commit/fc1bb663cac6846450ceb387751b491f2ecef13e
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Use clz, ctz for msb_pos, lsb_pos, if available

On many modern platforms these functions can be replaced by a single
machine instruction or two.  This commit looks for this possibility and
uses it if possible.


  Commit: e88dde507ccbbc2140c509d1e6b0a960d868c6d7
      https://github.com/Perl/perl5/commit/e88dde507ccbbc2140c509d1e6b0a960d868c6d7
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Use windows builtins for msb_pos, lsb_pos, if avail

Windows has different intrinsics than the previous commit added, with a
different API for counting leading/trailing zeros


  Commit: 250e5324a59b505b79ee7b1dc924b0e8e5b51f95
      https://github.com/Perl/perl5/commit/250e5324a59b505b79ee7b1dc924b0e8e5b51f95
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Comment why ffs() isn't used for lsbit_pos()


  Commit: 2e0bc9cea3bb80cb7c96411cf8e20977e0d9f8c5
      https://github.com/Perl/perl5/commit/2e0bc9cea3bb80cb7c96411cf8e20977e0d9f8c5
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  Always use any fast available msb/lsb method

Some platforms have a fast way to get the msb but not the lsb; others,
more rarely, have the reverse.  But using a few shift and the like
instructions allows us to reduce either instance to terms of the other.

This commit causes any available fast method to be used by turning the
non-available case into the available one


  Commit: 4a1b7bb2bdf3d5a25e306752e4471e21093db314
      https://github.com/Perl/perl5/commit/4a1b7bb2bdf3d5a25e306752e4471e21093db314
  Author: Karl Williamson <khw@cpan.org>
  Date:   2021-07-30 (Fri, 30 Jul 2021)

  Changed paths:
    M inline.h

  Log Message:
  -----------
  msb_pos(): Bit twiddle a subtraction into an xor

Experiments by Tomasz Konojacki indicated that gcc, for one, doesn't
optimally optimize a subtraction from 2**n-1.  This commit tells the
compiler the optimization.


Compare: https://github.com/Perl/perl5/compare/6e7a7813c390...4a1b7bb2bdf3
[prev in list] [next in list] [prev in thread] [next in thread]