in reply to Optimizing a Text Canvas: An inner loop and a cloner

I'm not really much of a Perl optimization expert, but a couple things I noticed:
  1. You can get in and out of the sub a little faster by passing and returning refs instead of lists or strings. This minimizes the amount of data that needs to be copied onto the stack and then pulled back off. It would be a very minor gain per call, but, if 6000 calls in 0.25 second is normal, it may add up enough to be noticable.

  2. push can be surprisingly expensive due to the memory allocation overhead. You can mitigate this by setting the size of your array up front ($#a = $sw) and then inserting elements by index. You could also pre-size the array by initializing it with my @a = $blank x $sw.

  3. Try $chr || $blank instead of ?: - logical OR tends to be faster than doing a comparison, although they're not equivalent if $chr == 0.

  4. Another way around push would be to build the array contents directly in the join statement, presumably with map. It could get a bit convoluted in this case, since different bytes are determined by different methods, but, based on articles I've read, it sounds like this should be the fastest way to go if you can get an efficient mapping worked out.

  5. Instead of testing each attribute separately, try packing all of them into a single value, then just compare that from one iteration to the next and you'll save yourself half the dereferences/array lookups (since each structure will only need to be inspected once) and up to 80% of your comparisons (since it'll just be a single ne instead of 2 nes and 3 !=s). Something like: 
    $chr = $line->[$col] || $blank;
$atr = $arow->[$col];
$array_position++;
$curr_attribs = $atr->[AS_BG] . $atr->[AS_FG] . $atr->[AS_U] . $atr->[
+AS_BOLD] . $atr->[AS_BLINK];
if ($curr_attribs ne $last_attribs) {
  $a[$array_position] = _attr($atr) . $chr;
} else {
  $a[$array_position] = $chr;
}
$last_attribs = $curr_attribs;

    [download]
    If it's possible to render AS_BG and AS_FG into small enough integers (i.e., if you're dealing with 16 or 256 colors instead of full-bore 24-bit color), then $curr_attribs/$last_attribs could be bitfields instead of strings, which would allow a numeric comparison and probably speed things up even more.

OK, I think I've run out of ideas... Hopefully these will improve things enough to spare you the horrors of C.

Replies are listed 'Best First'.
Re^2: Optimizing a Text Canvas: An inner loop and a cloner
by JosiahBryan (Novice) on Jul 06, 2007 at 15:45 UTC

    Wow - great ideas...I'll work in trying them out ASAP.

    BTW, the AS_BG and AS_FG fields hold standard ANSI FG/BG color codes - e.g. ^[Xm, where X is 30-37 for FG and 40-47 for BG. So, yes, the BG and FG fields could be converted to an integer 0-7 or 10-17, then just add 30 to the resulting output. (Or just use 30-37, 40-47 for the values themselves - doesn't save any bytes to use 0-17.)

    However, I've never been very good with bitfields - could you be so kind as to offer a code example of how using bitfields would work? (My apologies for the simplistic question.)

[reply]

      Right, I think I've got a bit figured out on the bitfields. However, this doesn't work as expected: 

      
use constant AS_BG    => 0;
use constant AS_FG    => 8;
use constant AS_U     => 16;
use constant AS_BLINK => 17;
use constant AS_BOLD  => 18;

my $test = 0;

#$test |= ($v << $k);  # set $k to $v
#$test &= ~($v << $k); # 
print "Test0:[$test]\n";
$test |= 41 << AS_BG;
$test |= 31 << AS_FG;
$test |= 0 << AS_U;
$test |= 0 << AS_BLINK;
$test |= 1 << AS_BOLD;
print "Test1:[$test]\n";
print "Test parts: ".($test >> AS_BG).", ".($test>>AS_FG).",".($test>>
+AS_U).",".($test>>AS_BLINK).",".($test>>AS_BOLD)."\n";

      [download]
      Output: 
      Test0:[0]
Test1:[270121]
Test parts: 270121, 1055,4,2,1

      [download]

      Now, I'm sure I'm missing something here - but what? :-)

[reply]
[d/l]
[select]
      Sure. Assuming that the U/BOLD/BLINK attributes are 0/1 and that you've already converted your colors into integers (0-255) and copied all of your attribute settings into scalars (which you won't really want to do, but it simplifies the example), I would use: 
      $current_attribs = $as_bg + $as_fg << 8 + $as_u << 16 + $as_bold << 17
+ + $as_blink << 18;

      [download]
      This turns the full set of attributes into a 19-bit integer, allowing the CPU to compare two sets of attributes in a single operation when you check whether $current_attribs == $last_attribs. (They could be rendered into only 9 bits by taking the colors down into the 0-7 range (3 bits each instead of 8), but it would add a little time to do the conversion without saving any work later on.)
[reply]
[d/l]
[select]
        (In response to chatterbox questions...)

        To get the data back out from the bitfield, shift back to the right and use a logical bitwise AND to extract the relevant bits: 

        $as_bg    = $attribs       & 255;
$as_fg    = $attribs >> 8  & 255;
$as_u     = $attribs >> 16 & 1;
$as_bold  = $attribs >> 17 & 1;
$as_blink = $attrib  >> 18 & 1;

        [download]

        update: Corrected && to &.

[reply]
[d/l]

        Ahhhh...the lightbulb lites...I think I've got the idea. I'll play with it right now and see what I can come up with. (Many thanks for your help and patience.)

[reply]

In Section Seekers of Perl Wisdom