Fast string replace

user_1246115 0
Viewed 107

After building up a potentially very large string, I'm going to do a lot of changing single characters in it (or bytes, if necessary), to another char.

Actually, my script is building a crossword puzzle, so the string won't be very long, but my question is general:

How can I use the fact that I'm not altering the strings (or whatever data type is better) length, to speed things up?

I guess part of what I'm looking for is a way to send a pointer or reference to the string, or in Tcl's case the variable name.

My other question is what happens internally in the C code.

Will this call copy the entire string zero, one or even two times?

set index [expr {$row * $width + $col}]
set puzzle [string replace $puzzle $index $index "E"]
tcl
1 Answers

The string replace operation will do an in-place change provided two conditions are satisfied:

  1. The string being inserted must be the same length as the string being excised. I assume this one is obvious to you.
  2. The string must be in an unshared reference, so that nothing else can observe the value being modified. (This is a critical part of how all Tcl references work; shared references cannot be modified in-place.)

That call, as written, will copy. This is predictable based on simple examination of the reference handling for the string; the issue is that the old version of the string remains in puzzle until after the string replace completes (the set needs the result to work). To fix that, we do this slightly strange thing:

set puzzle [string replace $puzzle[set puzzle {}] $index $index "E"]

Yes, this is weird but it works well because concatenation with a known-empty string is an explicitly optimised case, assuming you're dealing with untraced variables here. (It'll work with traced variables, but the double write is observable and traces could do tricky things so you lose optimisation opportunities.)

If you were doing extensive changes that sometimes change the length of things, switching to using lists and lset would be more efficient. The equivalent operations on lists all use the same general reference and in-place semantics, but work on list elements instead of characters.

Disassembly

The optimisation I'm talking about is in the strcat opcode, and strreplace knows to do in-place when it can but you don't see the information at the bytecode level; virtually all operations know that.

% tcl::unsupported::disassemble lambda {{puzzle index} {
    set puzzle [string replace $puzzle[set puzzle {}] $index $index "E"]
}}
ByteCode 0x0x7fbff6021c10, refCt 1, epoch 17, interp 0x0x7fbff481e010 (epoch 17)
  Source "\n    set puzzle [string replace $puzzle[set puzzle {}]..."
  Cmds 3, src 74, inst 18, litObjs 2, aux 0, stkDepth 4, code/src 0.00
  Proc 0x0x7fbff601cc90, refCt 1, args 2, compiled locals 2
      slot 0, scalar, arg, "puzzle"
      slot 1, scalar, arg, "index"
  Commands 3:
      1: pc 0-16, src 5-72        2: pc 0-14, src 17-71
      3: pc 2-5, src 40-52
  Command 1: "set puzzle [string replace $puzzle[set puzzle {}] $inde..."
  Command 2: "string replace $puzzle[set puzzle {}] $index $index \"E..."
    (0) loadScalar1 %v0     # var "puzzle"
  Command 3: "set puzzle {}..."
    (2) push1 0     # ""
    (4) storeScalar1 %v0    # var "puzzle"
    (6) strcat 2 
    (8) loadScalar1 %v1     # var "index"
    (10) loadScalar1 %v1    # var "index"
    (12) push1 1    # "E"
    (14) strreplace 
    (15) storeScalar1 %v0   # var "puzzle"
    (17) done
user_3018320
Related