Tcl Source Code

View Ticket
Login
Ticket UUID: 3d1c409f1afbca6b74f824cffe8dbb4028a410c5
Title: Bad performance: tclThreadAlloc vs. CPU-cache (fragmentation/granularity/etc)...
Type: Bug Created on: 2024-11-18 14:11:40
Submitter: sebres Assigned to: nobody
Subsystem: 41. Memory Allocation Severity: Severe
Priority: 5 Medium Last modified: 2024-11-20 15:50:02
Status: Open Closed by: nobody
Resolution: None Closed on:
Version: any
Description:

(Just for the record, initially posted in chat in 2019 - paste.tclers.tk/5260).

Issue: the longer Tcl works - the slower it becomes...

The simplest example illustrating this:

  proc test {} {timerate -calibrate {incr i} 10000 10000000}; test; # calibrate overhead for incr
  proc test args {
    puts "set: [timerate { set a([incr i]) _ } {*}$args]"; 
    lset args 1 $i; set i 0; 
    puts "get: [timerate { set a([incr i]) } {*}$args]"
  }
  time { test 10000 1000000 } 50

Results:

* 1x-threaded:
    set: 0.153809 µs/# 1000000 # 6501570 #/sec 153.809 net-ms
    get: 0.049532 µs/# 1000000 # 20188968 #/sec 49.532 net-ms
    ... 100 times ...
    set: 0.598031 µs/# 1000000 # 1672154 #/sec 598.031 net-ms
    get: 0.331693 µs/# 1000000 # 3014836 #/sec 331.693 net-ms
* 16x-threaded:
    set * 16x: 0.573478 µs/# 4000000 # 291248 #/sec 2293.913 net-ms
    get * 16x: 0.077514 µs/# 4000000 # 14923264 #/sec 310.059 net-ms
    ... 20 times ...
    set * 16x: 3.539208 µs/# 4000000 # 304646 #/sec 14156.834 net-ms
    get * 16x: 0.519618 µs/# 4000000 # 2048606 #/sec 2078.474 net-ms

First problem - releasing of objects (and its followed holding in linked LIFO of object pool) may happen randomly, so the objects are distributed across different memory blocks (by the way, not considering cache coherency), and on further allocs becomes "fragmented" across different cache blocks, what'd cause many CPU-cache washouts and related reloads. Long fragmentation of such kind in the in object pool LIFO will only exacerbate the problem.

The second problem is that besides fragmentation/granularity, the single mem-block that gets "changed" in some thread, will cause that the whole block in cache needs to be invalidated for other threads, what in turn would cause more memory accesses (which is hundred times slower than L2 and thousand times slower than L1 access).

In my fork I fixed this "wrong" behaviour in my own threaded-alloc module, which prefers moving of whole free pages the single objects, and combining them to single free block instead of simplest LIFO in threaded object pool:

* 1x-threaded:
    set : 0.140644 µs/# 250000 # 7110150 #/sec 35.161 net-ms
    get : 0.018572 µs/# 250000 # 53844497 #/sec 4.643 net-ms
    ... 100 times ...
    set : 0.083600 µs/# 250000 # 11961722 #/sec 20.900 net-ms
    get : 0.017704 µs/# 250000 # 56484410 #/sec 4.426 net-ms
* 16x-threaded:
    set * 16x: 0.810806 µs/# 4000000 # 129652 #/sec 3243.227 net-ms
    get * 16x: 0.556715 µs/# 4000000 # 246766 #/sec 2226.860 net-ms
    ... 20 times ...
    set * 16x: 0.665778 µs/# 4000000 # 1671624 #/sec 2663.113 net-ms
    get * 16x: 0.343585 µs/# 4000000 # 3428775 #/sec 1374.340 net-ms
User Comments:
anonymous added on 2024-11-18 15:40:02:
> the longer Tcl works - the slower it becomes

Noticed as well, but couldn't catch and understand the reason. Congratulations Sergey and many thanks for your success at it.

jan.nijtmans added on 2024-11-20 13:55:11:

This sounds like a useful optimization!

Wondering how this compares with just using the system malloc/free. Does tclThreadAlloc() really have better performance, compared to modern malloc/free implementations?


sebres added on 2024-11-20 15:50:02:

> Does tclThreadAlloc() really have better performance, compared to modern malloc/free implementations?

Single-threaded it is marginally better, however the lot of the load remains in user space, and doesn't go in kernel time (syscalls), because Tcl works not in native ways with memory how any C/C++ programs would do, but everything (every object, var, hash-element) expects at least 1 allocation (mostly 2 or more) and alloc/free becomes a mass processing.
Multi-threaded it is many, many times superior, because mostly no locking happens (or coarse-grained locking only if more memory needed) and also touches the kernel rarely.

With OS allocator, I saw a tenfold degradation already on 4 threads. It is like GIL in python (not really that, but the effect looks indeed very similar, especially with growth in thread count).

So yes, a (smart) memory-manager is still a must for things like Tcl, even with modern OS. Surely with a disadvantage of in tcl-core reserved memory (what can also be solved with a GC, periodically freeing memory, and/or with periodical release of working threads, reaching some idle time).