From thkarcher@gmx.de

Created by tk@wh4f.de

Hi folks,

I got a performance problem with recursive multithreaded scripts on
multicore machines that really slows down the overall execution.

The following example script performs a simple multithreaded version of
merge sort and is recursive. It takes a file from the command line as
argument.

The results are fine and well sorted, but this bug report is about _how_
perl handles the recursive multithreading. When you start the program,
you see in "vmstat 1" a _lot_ of context switches. A lot means 10-100
times the normal rate. You can also see the effect when you "time" the
script. I noticed the effect not so much on a Dual Core machine, but on
an 8-Core machine, the context switches really slow down the script.
With non-recursive parallelism, no such effect occurs.

This is my sample script​:

#!/usr/bin/perl

use strict;
use warnings;
use threads;
use threads​::shared;
use Thread​::Queue;

my @​sortdata​:shared;

open (my $SORTFILE, '<', $ARGV[0]) or die ("File ".$ARGV[0]." could not
be opened.\n");
@​sortdata = <$SORTFILE>;
close ($SORTFILE);

my $size = @​sortdata;
# this parameter essentially affects the call depth of the recursive
multithreading
my $mergesortdepth = 2;

mergesort_string (0, $size, $mergesortdepth);

sub mergesort_string {
  my ($begin, $end, $threaddepth) = @​_;
  my $size = $end - $begin;

  if ($size < 2) {
  return;
  }
  my $half = $begin + int ($size / 2);

# this is the critical part​: $threaddepth decides wether we continue
multithreaded or not
  if ($threaddepth > 1) {
  my $firstmergesortthread = new threads (\&mergesort_string, $begin,
$half, $threaddepth - 1);
  my $secondmergesortthread = new threads (\&mergesort_string, $half,
$end, $threaddepth - 1);
  $firstmergesortthread->join ();
  $secondmergesortthread->join ();
  } else {
  mergesort_string ($begin, $half, 0);
  mergesort_string ($half, $end, 0);
  }

  for (my $i = $begin; $i < $half; ++$i) {
  if ($sortdata[$i] gt $sortdata[$half]) {
  my $v = $sortdata[$i];
  $sortdata[$i] = $sortdata[$half];

  my $i = $half;
  while ($i < $end - 1 && $sortdata[$i + 1] lt $v) {
  ($sortdata[$i], $sortdata[$i + 1]) =
  ($sortdata[$i + 1], $sortdata[$i]);
  ++$i;
  }
  $sortdata[$i] = $v;
  }
  }
  return;
}

Please come back to me if you need further input. Sorry for sending this
via my normal mail client, but there is no sendmail on the 8-Core
machine.

Thanks!

Thomas

Flags:
    category=library
    severity=medium

Site configuration information for perl 5.10.0:

Configured by Debian Project at Fri May  9 09:19:36 UTC 2008.

Summary of my perl5 (revision 5 version 10 subversion 0) configuration:
  Platform:
    osname=linux, osvers=2.6.24-15-server,
archname=x86_64-linux-gnu-thread-multi
    uname='linux crested 2.6.24-15-server #1 smp mon apr 7 17:10:32 utc
2008 x86_64 gnulinux '
    config_args='-Dusethreads -Duselargefiles -Dccflags=-DDEBIAN
-Dcccdlflags=-fPIC -Darchname=x86_64-linux-gnu -Dprefix=/usr
-Dprivlib=/usr/share/perl/5.10 -Darchlib=/usr/lib/perl/5.10
-Dvendorprefix=/usr -Dvendorlib=/usr/share/perl5
-Dvendorarch=/usr/lib/perl5 -Dsiteprefix=/usr/local
-Dsitelib=/usr/local/share/perl/5.10.0
-Dsitearch=/usr/local/lib/perl/5.10.0 -Dman1dir=/usr/share/man/man1
-Dman3dir=/usr/share/man/man3 -Dsiteman1dir=/usr/local/man/man1
-Dsiteman3dir=/usr/local/man/man3 -Dman1ext=1 -Dman3ext=3perl
-Dpager=/usr/bin/sensible-pager -Uafs -Ud_csh -Ud_ualarm -Uusesfio
-Uusenm -DDEBUGGING=-g -Doptimize=-O2 -Duseshrplib
-Dlibperl=libperl.so.5.10.0 -Dd_dosuid -des'
    hint=recommended, useposix=true, d_sigaction=define
    useithreads=define, usemultiplicity=define
    useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
    use64bitint=define, use64bitall=define, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-D_REENTRANT -D_GNU_SOURCE -DDEBIAN
-fno-strict-aliasing -pipe -I/usr/local/include -D_LARGEFILE_SOURCE
-D_FILE_OFFSET_BITS=64',
    optimize='-O2 -g',
    cppflags='-D_REENTRANT -D_GNU_SOURCE -DDEBIAN -fno-strict-aliasing
-pipe -I/usr/local/include'
    ccversion='', gccversion='4.3.1 20080430 (prerelease)',
gccosandvers=''
    intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
    ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t',
lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='cc', ldflags =' -L/usr/local/lib'
    libpth=/usr/local/lib /lib /usr/lib /lib64 /usr/lib64
    libs=-lgdbm -lgdbm_compat -ldb -ldl -lm -lpthread -lc -lcrypt
    perllibs=-ldl -lm -lpthread -lc -lcrypt
    libc=/lib/libc-2.7.so, so=so, useshrplib=true,
libperl=libperl.so.5.10.0
    gnulibc_version='2.7'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
    cccdlflags='-fPIC', lddlflags='-shared -O2 -g -L/usr/local/lib'

Locally applied patches:
    


@INC for perl 5.10.0:
    /etc/perl
    /usr/local/lib/perl/5.10.0
    /usr/local/share/perl/5.10.0
    /usr/lib/perl5
    /usr/share/perl5
    /usr/lib/perl/5.10
    /usr/share/perl/5.10
    /usr/local/lib/site_perl
    .


Environment for perl 5.10.0:
    HOME=/home/tkarcher
    LANG=de_DE.UTF-8
    LANGUAGE (unset)
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)

PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games
    PERL_BADLANG (unset)
    SHELL=/bin/bash

From @rgs

2008/6/10 via RT Thomas Karcher <perlbug-followup@​perl.org>​:

I got a performance problem with recursive multithreaded scripts on
multicore machines that really slows down the overall execution.

The following example script performs a simple multithreaded version of
merge sort and is recursive. It takes a file from the command line as
argument.

The results are fine and well sorted, but this bug report is about _how_
perl handles the recursive multithreading. When you start the program,
you see in "vmstat 1" a _lot_ of context switches. A lot means 10-100
times the normal rate. You can also see the effect when you "time" the
script. I noticed the effect not so much on a Dual Core machine, but on
an 8-Core machine, the context switches really slow down the script.
With non-recursive parallelism, no such effect occurs.

I think that's a bit expected. Perl threads don't share anything by
default, meaning that launching a new thread in Perl clones the whole
interpreter (there's no COW yet), and that's very expensive.

The RT System itself - Status changed from 'new' to 'open'

From thkarcher@gmx.de

Hi Rafael,

just to add some information​: I didn't mean just during thread creation
(I created about 5-20 threads overall) but while they are actually
running ... so I suppose it's not about cloning during thread
creation only ...

Thomas

From thkarcher@gmx.de

Hi Rafael,

just to add some information​: I didn't mean just during thread creation
(I created about 5-20 threads overall) but while they are actually
running ... so I suppose it's not about cloning during thread
creation ...

Regards,
Thomas

From thkarcher@gmx.de

Hi,

as follow-up​: The massive amounts of context switches is probably caused
by the global lock on @​sortdata, which is shared among the threads and
changed a lot. Perl doesn't seem to provide a fine-granular locking
mechanism for arrays.

See also​:
http​://www.nntp.perl.org/group/perl.ithreads/2008/09/msg1323.html

Decide for yourself if this is considered a bug or just an intended but
not-well scaling behaviour ... :)

Thanks,
Thomas