CUFP
diotalevi
<p>In a reply to [id://732407], I suggested that [mod://Judy::1]/[http://judy.sourceforge.net/doc/Judy1_3x.htm|Judy1(3)] was a sparse bit vector which might be interesting as a replacement for vec(). Perl's built-in vec can also be used as a bit vector but it's not sparse - all bits between the zeroth to the highest ever set are instantiated inside a perl string. This is only convenient if your bit vector isn't too big in ram.</p>
<h2>Example code</h2>
<p>A simple perl bit vector</p><c>use constant MEGABYTE => 2 ** 20;
my $vector = '';
# 5,000 bits. Set every 100th bit between 15 million and 20 million.
for ( 15_000_000 .. 20_000_000 ) {
if ( ! ( $_ % 100 ) ) {
vec( $vector, $_, 1 ) = 1;
}
}
printf "%0.1fM\n", length( $vector ) / MEGABYTE;</c>
<p>A simple Judy::1 bit vector</p><c>use constant KILOBYTE => 2 ** 10;
use Judy::1 qw( Set MemUsed );
my $vec;
# 5,000 bits. Set every 100th bit between 15 million and 20 million.
for ( 15_000_000 .. 20_000_000 ) {
if ( ! ( $_ % 100 ) ) {
Set( $judy, $_ );
}
}
printf "%0.1fK\n", MemUsed( $judy ) / KILOBYTE;</c>
<h2>Memory "benchmarks"</h2>
<table>
<tr><th>Density</th><th>vec()</th><th>Judy::1</th></tr>
<tr><td colspan="3">Tests using the entire range 0..20,000,000</td></tr>
<tr><td>Every bit</td><td>2.3M</td><td>618K</td></tr>
</table>
<table>
<tr><th>Density</th><th>vec()</th><th>Judy::1</th></tr>
<tr><td colspan="3">Tests using range 15,000,000..20,000,000</td></tr>
<tr><td>Every bit</td><td>2.3M</td><td>162K</td></tr>
<tr><td>Every 10th bit</td><td>2.3M</td><td>772K</td></tr>
<tr><td>Every 100th bit</td><td>2.3M</td><td>158K</td></tr>
<tr><td>Every 1000th bit</td><td>2.3M</td><td>65K</td></tr>
</table>
<div class="pmsig"><div class="pmsig-194920">
<p>⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊</p>
</div></div>