 Do you know where your variables are? PerlMonks

### Re^2: Optimizing with Caching vs. Parallelizing (MCE::Map)

by marioroy (Parson)
 on Apr 20, 2020 at 19:07 UTC Need Help??

Hi rjt,

Thank you for this challenge. This consumed so much of my time in a great way. The reason is partly due to, "What if possible for many CPU cores?" But first made attempts for fast using 1 core. Below are the 3 progressive solutions, each one running faster.

Update: Added results from two machines.

Laurent's demonstration plus updates:

```#!/usr/bin/env perl
use strict;
use warnings;

my \$size = shift || 1e6;

\$size = 1e6 if \$size < 1e6;  # minimum
\$size = 1e9 if \$size > 1e9;  # maximum

##
# Laurent's demonstration + updates
#   https://www.perlmonks.org/?node_id=11115520
#   https://www.perlmonks.org/?node_id=11115540
#
# Parallel solution
#   https://www.perlmonks.org/?node_id=11115544
##

my @cache = (0, 1, 2);
my @seqs;

sub collatz_seq {
my \$size = shift;
my (\$n, \$steps);
for my \$input (2..\$size) {
\$n = \$input, \$steps = 0;
while (\$n != 1) {
\$steps += \$cache[\$n], last if defined \$cache[\$n];
\$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 )
: ( \$steps += 1, \$n = \$n >> 1 );
}
\$cache[\$input] = \$steps if \$input < \$size;
push @seqs, [ \$input, \$steps ] if \$steps > 400;
}
}

collatz_seq(\$size);
@seqs = ( sort { \$b-> <=> \$a->} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @\$_
for @seqs;
[download]```

iM71's C++ demonstration converted to Perl plus updates:

```#!/usr/bin/env perl
use strict;
use warnings;

my \$size = shift || 1e6;

\$size = 1e6 if \$size < 1e6;  # minimum
\$size = 1e9 if \$size > 1e9;  # maximum

##
# iM71's demonstration + applied T(x) notation and compression
#   https://stackoverflow.com/a/55361008
#   https://www.youtube.com/watch?v=t1I9uHF9X5Y (1 min into video)
#
# Parallel solution
#   https://www.perlmonks.org/?node_id=11115780
##

my @cache = (0, 1, 2);
my @seqs;

sub collatz_seq {
my \$size = shift;
my (\$n, \$steps);
for my \$input (2..\$size) {
\$n = \$input, \$steps = 0;
\$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 )
: ( \$steps += 1, \$n = \$n >> 1 )
while \$n != 1 && \$n >= \$input;

\$cache[\$input] = \$steps += \$cache[\$n];
push @seqs, [ \$input, \$steps ] if \$steps > 400;
}
}

collatz_seq(\$size);
@seqs = ( sort { \$b-> <=> \$a->} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @\$_
for @seqs;
[download]```

Step counting using Inline C:

```#!/usr/bin/env perl
use strict;
use warnings;

use Inline C => Config => CCFLAGSEX => '-O2 -fomit-frame-pointer';
use Inline C => <<'END_OF_C_CODE';

#include <stdint.h>

void num_steps_c( SV* _n, SV* _s )
{
uint64_t n, input;
int steps = 0;

n = input = SvUV(_n);

while ( n != 1 && n >= input ) {
n % 2 ? ( steps += 2, n = (3 * n + 1) >> 1 )
: ( steps += 1, n = n >> 1 );
}

sv_setuv(_n, n);
sv_setiv(_s, steps);

return;
}

END_OF_C_CODE

my \$size = shift || 1e6;

\$size = 1e6 if \$size < 1e6;  # minimum
\$size = 1e9 if \$size > 1e9;  # maximum

##
# iM71's demonstration + applied T(x) notation and compression
#   https://stackoverflow.com/a/55361008
#   https://www.youtube.com/watch?v=t1I9uHF9X5Y (1 min into video)
#
# Parallel solution
#   https://www.perlmonks.org/?node_id=11115780
##

my @cache = (0, 1, 2);
my @seqs;

sub collatz_seq {
my \$size = shift;
my (\$n, \$steps);
for my \$input (2..\$size) {
num_steps_c(\$n = \$input, \$steps);
\$cache[\$input] = \$steps += \$cache[\$n];
push @seqs, [ \$input, \$steps ] if \$steps > 400;
}
}

collatz_seq(\$size);
@seqs = ( sort { \$b-> <=> \$a->} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @\$_
for @seqs;
[download]```

Results from two machines:

```64-bit VM:
rjt   0.903s
Laurent + updates   0.696s
iM71 + updates   0.602s
Step counting in C   0.273s (1st time involves compiling)

AMD 3970x:
rjt   0.635s
Laurent + updates   0.516s
iM71 + updates   0.467s
Step counting in C   0.191s (1st time involves compiling)

Collatz(837799) has sequence length of 525 steps
Collatz(626331) has sequence length of 509 steps
Collatz(939497) has sequence length of 507 steps
Collatz(704623) has sequence length of 504 steps
Collatz(910107) has sequence length of 476 steps
Collatz(927003) has sequence length of 476 steps
Collatz(511935) has sequence length of 470 steps
Collatz(767903) has sequence length of 468 steps
Collatz(796095) has sequence length of 468 steps
Collatz(970599) has sequence length of 458 steps
Collatz(546681) has sequence length of 452 steps
Collatz(818943) has sequence length of 450 steps
Collatz(820022) has sequence length of 450 steps
Collatz(820023) has sequence length of 450 steps
Collatz(410011) has sequence length of 449 steps
Collatz(615017) has sequence length of 447 steps
Collatz(886953) has sequence length of 445 steps
Collatz(906175) has sequence length of 445 steps
Collatz(922524) has sequence length of 445 steps
Collatz(922525) has sequence length of 445 steps
[download]```

Regards, Mario

Replies are listed 'Best First'.
Re^3: Optimizing with Caching vs. Parallelizing (MCE::Map)
by rjt (Curate) on Apr 20, 2020 at 20:48 UTC

This is great, Mario (and everyone else in this thread, for that matter)! The multicore work is fantastic. I'm very impressed by the level of interest and dedication this "little" question generated. Hopefully we can come up with a few more like it. (And anyone can suggest challenges, by the way.)

use strict; use warnings; omitted for brevity.

Hi rjt and fellow Monks,

I updated the parallel demonstrations here and here to ensure orderly output plus cache miss update for parallel iM71. Then captured results for 1e8. Note that running parallel involves File::Map, pack, and unpack. Running Inline::C involves compiling C code on the first run.

Testing was done on a Windows 10 host inside a Docker container running Ubuntu 18.04.x and Perl 5.30.1. The hardware is an AMD 3970x box (32-cores with SMT disabled).

1e8 Output:

```Collatz(63728127) has sequence length of 950 steps
Collatz(95592191) has sequence length of 948 steps
Collatz(96883183) has sequence length of 811 steps
Collatz(86010015) has sequence length of 798 steps
Collatz(98110761) has sequence length of 749 steps
Collatz(73583070) has sequence length of 746 steps
Collatz(73583071) has sequence length of 746 steps
Collatz(36791535) has sequence length of 745 steps
Collatz(55187303) has sequence length of 743 steps
Collatz(56924955) has sequence length of 743 steps
Collatz(82780955) has sequence length of 741 steps
Collatz(85387433) has sequence length of 741 steps
Collatz(63101607) has sequence length of 738 steps
Collatz(64040575) has sequence length of 738 steps
Collatz(93128574) has sequence length of 736 steps
Collatz(93128575) has sequence length of 736 steps
Collatz(94652411) has sequence length of 736 steps
Collatz(96060863) has sequence length of 736 steps
Collatz(46564287) has sequence length of 735 steps
Collatz(69846431) has sequence length of 733 steps
[download]```

Performance:

```1e8: parallel, 32 cores (File::Map, pack, unpack):
https://www.perlmonks.org/?node_id=11115544
https://www.perlmonks.org/?node_id=11115780

Laurent + updates    3.474s
iM71 + updates    2.701s
Step counting in C    1.654s

1e8: parallel, 16 cores

Laurent + updates    6.219s
iM71 + updates    4.787s
Step counting in C    2.793s

1e8: parallel,  8 cores

Laurent + updates   12.061s
iM71 + updates    9.200s
Step counting in C    5.258s

1e8: parallel,  4 cores

Laurent + updates   23.615s
iM71 + updates   17.935s
Step counting in C   10.056s

1e8: parallel,  2 cores

Laurent + updates   46.146s
iM71 + updates   34.342s
Step counting in C   19.084s

1e8: non-parallel (Array):
https://www.perlmonks.org/?node_id=11115841

Laurent + updates   53.961s
iM71 + updates   48.673s
Step counting in C   19.023s
[download]```

Parallel now matches serial for sequences with equal number of steps (i.e. smallest sequence first).

Regards, Mario

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11115841]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (9)
As of 2021-04-15 18:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?