X-Git-Url: http://git.vpit.fr/?p=perl%2Fmodules%2FScalar-Vec-Util.git;a=blobdiff_plain;f=README;h=85bc263cebd239957c87e76601044870c8345dc4;hp=69aa06bc0b036be56553a43c7ad6eaeb633381a2;hb=HEAD;hpb=2ae36849ba8e31e2e90b1ee1bfb6c73159d47cc6 diff --git a/README b/README index 69aa06b..85bc263 100644 --- a/README +++ b/README @@ -2,66 +2,205 @@ NAME Scalar::Vec::Util - Utility routines for vec strings. VERSION - Version 0.02 + Version 0.08 SYNOPSIS - use Scalar::Vec::Util qw/vfill vcopy veq/; + use Scalar::Vec::Util qw; my $s; vfill $s, 0, 100, 1; # Fill with 100 bits 1 starting at 0. my $t; vcopy $s, 20, $t, 10, 30; # Copy 30 bits from $s, starting at 20, # to $t, starting at 10. - vcopy $t, 10, $t, 20, 30; # Overalapping areas DWIM. + vcopy $t, 10, $t, 20, 30; # Overlapping areas DWIM. if (veq $t, 10, $t, 20, 30) { ... } # Yes, they are equal now. DESCRIPTION - A set of utilities to manipulate bits in vec strings. Highly optimized - XS routines are used when available, but straightforward pure perl - replacements are also provided for platforms without a C compiler. + This module provides a set of utility routines that efficiently + manipulate bits in vec strings. Highly optimized XS functions are used + whenever possible, but straightforward pure Perl replacements are also + available for platforms without a C compiler. - This module doesn't reimplement bit vectors. It can be used on the very - same scalars that "vec" builds, or actually on any Perl string - ("SVt_PV"). + Note that this module does not aim at reimplementing bit vectors : all + its functions can be used on any Perl string, just like "vec" in + perlfunc. CONSTANTS "SVU_PP" - True when pure perl fallbacks are used instead of XS functions. + True when pure Perl fallbacks are used instead of XS functions. "SVU_SIZE" - Size in bits of the unit used for moves. The higher this value is, the - faster the XS functions are. It's usually "CHAR_BIT * + The size (in bits) of the unit used for bit operations. The higher this + value is, the faster the XS functions are. It is usually "CHAR_BIT * $Config{alignbytes}", except on non-little-endian architectures where it currently falls back to "CHAR_BIT" (e.g. SPARC). FUNCTIONS - "vfill $vec, $start, $length, $bit" - Starting at $start in $vec, fills $length bits with $bit. Grows $vec if - necessary. + "vfill" + vfill $vec, $start, $length, $bit; + + Starting at $start in $vec, fills $length bits with ones if $bit is true + and with zeros if $bit is false. + + $vec is upgraded to a string and extended if necessary. Bits that are + outside of the specified area are left untouched. + + "vcopy" + vcopy $from => $from_start, $to => $to_start, $length; - "vcopy $from => $from_start, $to => $to_start, $length" Copies $length bits starting at $from_start in $from to $to_start in - $to. If "$from_start + $length" is too long for $from, zeros are copied - past $length. Grows $to if necessary. + $to. + + $from and $to are allowed to be the same scalar, and the given areas can + rightfully overlap. + + $from is upgraded to a string if it isn't one already. If "$from_start + + $length" goes out of the bounds of $from, then the extra bits are + treated as zeros. $to is upgraded to a string and extended if necessary. + The content of $from is not modified, except when it is equal to $to. + Bits that are outside of the specified area are left untouched. + + This function does not need to allocate any extra memory. + + "vshift" + vshift $v, $start, $length => $bits, $insert; + + In the area starting at $start and of length $length in $v, shift bits + "abs $bits" positions left if "$bits > 0" and right otherwise. + + When $insert is defined, the resulting gap is also filled with ones if + $insert is true and with zeros if $insert is false. + + $v is upgraded to a string if it isn't one already. If "$start + + $length" goes out of the bounds of $v, then the extra bits are treated + as zeros. Bits that are outside of the specified area are left + untouched. + + This function does not need to allocate any extra memory. + + "vrot" + vrot $v, $start, $length, $bits; + + In the area starting at $start and of length $length in $v, rotates bits + "abs $bits" positions left if "$bits > 0" and right otherwise. + + $v is upgraded to a string if it isn't one already. If "$start + + $length" goes out of the bounds of $v, then the extra bits are treated + as zeros. Bits that are outside of the specified area are left + untouched. + + This function currently allocates an extra buffer of size "O($bits)". + + "veq" + veq $v1 => $v1_start, $v2 => $v2_start, $length; - "veq $v1 => $v1_start, $v2 => $v2_start, $length" Returns true if the $length bits starting at $v1_start in $v1 and - $v2_start in $v2 are equal, and false otherwise. If needed, $length is - decreased to fit inside $v1 and $v2 boundaries. + $v2_start in $v2 are equal, and false otherwise. + + $v1 and $v2 are upgraded to strings if they aren't already, but their + contents are never modified. If "$v1_start + $length" (respectively + "$v2_start + $length") goes out of the bounds of $v1 (respectively $v2), + then the extra bits are treated as zeros. + + This function does not need to allocate any extra memory. EXPORT - The functions "vfill", "vcopy" and "veq" are only exported on request. - All of them are exported by the tags ':funcs' and ':all'. + The functions "vfill", "vcopy", "vshift", "vrot" and "veq" are only + exported on request. All of them are exported by the tags ':funcs' and + ':all'. The constants "SVU_PP" and "SVU_SIZE" are also only exported on request. They are all exported by the tags ':consts' and ':all'. +BENCHMARKS + The following timings were obtained by running the "samples/bench.pl" + script. The "_pp" entries are the pure Perl versions, whereas "_bv" are + Bit::Vector versions. + + * This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64 + bits). + + Filling bits at a given position : + Rate vfill_pp vfill_bv vfill + vfill_pp 80.3/s -- -100% -100% + vfill_bv 1053399/s 1312401% -- -11% + vfill 1180792/s 1471129% 12% -- + + Copying bits from a bit vector to a different one : + Rate vcopy_pp vcopy_bv vcopy + vcopy_pp 112/s -- -100% -100% + vcopy_bv 62599/s 55622% -- -89% + vcopy 558491/s 497036% 792% -- + + Moving bits in the same bit vector from a given position + to a different one : + Rate vmove_pp vmove_bv vmove + vmove_pp 64.8/s -- -100% -100% + vmove_bv 64742/s 99751% -- -88% + vmove 547980/s 845043% 746% -- + + Testing bit equality from different positions of different + bit vectors : + Rate veq_pp veq_bv veq + veq_pp 92.7/s -- -100% -100% + veq_bv 32777/s 35241% -- -94% + veq 505828/s 545300% 1443% -- + + * This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits). + + Rate vfill_pp vfill_bv vfill + vfill_pp 185/s -- -100% -100% + vfill_bv 407979/s 220068% -- -16% + vfill 486022/s 262184% 19% -- + + Rate vcopy_pp vcopy_bv vcopy + vcopy_pp 61.5/s -- -100% -100% + vcopy_bv 32548/s 52853% -- -83% + vcopy 187360/s 304724% 476% -- + + Rate vmove_pp vmove_bv vmove + vmove_pp 63.1/s -- -100% -100% + vmove_bv 32829/s 51933% -- -83% + vmove 188572/s 298787% 474% -- + + Rate veq_pp veq_bv veq + veq_pp 34.2/s -- -100% -100% + veq_bv 17518/s 51190% -- -91% + veq 192181/s 562591% 997% -- + + * This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits). + + Rate vfill_pp vfill vfill_bv + vfill_pp 4.23/s -- -100% -100% + vfill 30039/s 709283% -- -17% + vfill_bv 36022/s 850568% 20% -- + + Rate vcopy_pp vcopy_bv vcopy + vcopy_pp 2.74/s -- -100% -100% + vcopy_bv 8146/s 297694% -- -60% + vcopy 20266/s 740740% 149% -- + + Rate vmove_pp vmove_bv vmove + vmove_pp 2.66/s -- -100% -100% + vmove_bv 8274/s 311196% -- -59% + vmove 20287/s 763190% 145% -- + + Rate veq_pp veq_bv veq + veq_pp 7.33/s -- -100% -100% + veq_bv 2499/s 33978% -- -87% + veq 19675/s 268193% 687% -- + CAVEATS Please report architectures where we can't use the alignment as the move unit. I'll add exceptions for them. DEPENDENCIES - Carp, Exporter (core modules since perl 5), XSLoader (since perl 5.006). + perl 5.6. + + A C compiler. This module may happen to build with a C++ compiler as + well, but don't rely on it, as no guarantee is made in this regard. + + Carp, Exporter (core modules since perl 5), XSLoader (since perl 5.6.0). SEE ALSO Bit::Vector gives a complete reimplementation of bit vectors. @@ -69,8 +208,7 @@ SEE ALSO AUTHOR Vincent Pit, "", . - You can contact me by mail or on #perl @ FreeNode (vincent or - Prof_Vince). + You can contact me by mail or on "irc.perl.org" (vincent). BUGS Please report any bugs or feature requests to "bug-scalar-vec-util at @@ -88,7 +226,8 @@ SUPPORT . COPYRIGHT & LICENSE - Copyright 2008 Vincent Pit, all rights reserved. + Copyright 2008,2009,2010,2011,2012,2013 Vincent Pit, all rights + reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.