It will generate a picture something like this[but with color]

https://upload.wikimedia.org/wikipedia/commons/f/f8/Sierpinski_m100000.png

I wrote it first, a perl script:

#!/usr/bin/perl
use Cairo;

my $size    = 2000;
my $border  = 10;
my $level   = 12;
my $image   = 'perl.png';
my $surface = Cairo::ImageSurface->create( 'argb32', $size, $size );
my $cr      = Cairo::Context->create($surface);

sub X()     { 0 }
sub Y()     { 1 }
sub head()  { 0 }
sub left()  { 1 }
sub right() { 2 }
sub some    { $level, @_ }

sub triangle {
    my $x        = $size / 2 - $border;
    my $y        = $x * sqrt 3;
    my $v        = ( $size - $y ) / 2;
    my $triangle = [
        [ $size / 2,       $v ],
        [ $border,         $size - $v ],
        [ $size - $border, $size - $v ]
    ];
    [$triangle]

}

sub fill {
    my ( $left, $right, $tail ) = @_;
    my @color = (
        ( $size - $tail->[Y] ) / $size,
        ( $size - $tail->[X] ) / $size,
        $tail->[X] / $size
    );
    $cr->set_source_rgb(@color);
    $cr->move_to(@$left);
    $cr->line_to(@$right), $cr->line_to(@$tail);
    $cr->fill;
}

sub draw {
    my ( $level, $triangle ) = @_;
    return unless $level;
    my $x = ( $triangle->[0][head][X] - $triangle->[0][left][X] ) / 2;
    return if $x < 1;
    my $y = ( $triangle->[0][left][Y] - $triangle->[0][head][Y] ) / 2;
    
    my @next = map {
        my ( $HEAD, $LEFT, $RIGHT ) = @$_;
        my $left = [ $HEAD->[X] - $x, $HEAD->[Y] + $y ];
        my $right = [ $HEAD->[X] + $x, $HEAD->[Y] + $y ];
        my $tail = [ $HEAD->[X], $LEFT->[Y] ];
        
        fill $left, $right, $tail;
        
        [ $HEAD,    $left, $right ],
          [ $left,  $LEFT, $tail ],
          [ $right, $tail, $RIGHT ]
    } @$triangle;
    
    draw( $level - 1, \@next );
}

sub go {
    $cr->rectangle( 0, 0, $size, $size );
    $cr->fill;
    $cr->set_line_width(.5);
    draw some triangle;
    $surface->write_to_png($image);
}

go;

and then. I translate it to nim:

import math, cairo

type point = tuple[x, y: float]
type trian = tuple[head, left, right: point]
type trias = seq[trian]

let
    size  : float = 2000
    border: float = 10
    level = 12
    image = "nim.png"

var
    surface: PSurface
    cr: PContext

proc triangle: trian =
    let x = size / 2.0 - border
    let y = x * 3.float64.sqrt
    let v = (size - y) / 2.0
    
    ((size / 2.0, v), (border, size - v), (size - border, size - v))

proc fill(left, right, tail: point) =
    let
        r = ( size - tail.y ) / size
        g = ( size - tail.x ) / size
        b = tail.x / size
    
    cr.set_source_rgb(r, g, b)
    cr.move_to(left.x, left.y)
    cr.line_to(right.x, right.y)
    cr.line_to(tail.x, tail.y)
    cr.fill

proc draw(level: int, ts: trias): trias =
    if level == 0: return
    let x = (ts[0].head.x - ts[0].left.x) / 2.0
    if x < 1.0: return
    let y = (ts[0].left.y - ts[0].head.y) / 2.0
    var next: trias
    for it in ts:
        let (HEAD, LEFT, RIGHT) = it
        let left  = (HEAD.x - x, HEAD.y + y)
        let right = (HEAD.x + x, HEAD.y + y)
        let tail  = (HEAD.x, LEFT.y)
        fill left, right, tail
        next = next & @[(HEAD, left, right), (left, LEFT, tail), (right, tail, RIGHT)]
    
    draw( level - 1, next )

proc go =
    let SIZE = size.int32
    surface = image_surface_create(TFORMAT.FORMAT_ARGB32, SIZE, SIZE)
    cr = surface.create
    cr.rectangle(0, 0, size, size)
    cr.fill
    cr.set_line_width 0.5
    let t1 = @[triangle()]
    discard draw(level, t1)
    discard surface.write_to_png image

go()

the time:

perl: 2.3s
nim: 9.0s [--cc=gcc, -d:release]
My question is:
1: Why it is so slow? my nim code.
2: How to speed up my nim code?

2017-02-24 06:07:18
Replace this line next = next & @[(HEAD, left, right), (left, LEFT, tail), (right, tail, RIGHT)] with next.add(...) and init var next: trias = @[].
2017-02-24 08:17:36
I typed up my answer. I was ready to post. I hit preview, and... Araq beat me by a few minutes! Oh well, maybe this post would still have some value...

I get similar results: the perl program is about three times faster.

OK, let's use Time::HiRes, import times (etc) for some ad-hoc time-subtracting.

About 24.5% of the Nim program's execution time is spent on surface.write_to_png image, which is actually a bit faster than Perl, so the cairo bindings are not the problem.

About 75% of the Nim program's execution time is spent on draw(level, t1). That proc uses recurses multiple times (level 12 to 3), but it uses about 69% of the total program time when level is 4, in which case the loop is executed 6561 times. So let's zoom in on this loop...

Wowzers, 88% of the time in that inner loop is spent just on concatenating seqs! So that is our problem...

I don't know what the best solution is, but one step in the right direction would be to allocate next before the for loop in draw():

var next: trias = newSeq[trian]()

And to use add inside the loop:

next.add @[
  (HEAD, left, right),
  (left, LEFT, tail),
  (right, tail, RIGHT)
]

And now we're 18% faster than perl.

2017-02-24 08:44:04
Araq, Libman thanks!! 2017-03-16 02:08:17

I had a related question: are seq preemptively allocating space for further additions?

If so, is there already a way to disable that? If not so, is there already a way to enable that?

2017-03-16 10:53:40
Yes certainly. There is no real way to disable it but you can use newSeqOfCap.
2017-03-16 11:06:36