test binarytrees working with only one thread

[C-Ackerman]

Version

v16.14.2

Platform

Linux chen 5.13.0-39-generic #44~20.04.1-Ubuntu SMP Thu Mar 24 16:43:35 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

Subsystem

No response

What steps will reproduce the bug?

Node executes 1.js and then uses top -H -p to view, only one thread works 100%, but the v12.18.4 version can execute concurrently with multiple threads，So when the amount of operation of the tree is large enough, v12 is more than v
16 operations are fast
https://github.com/hanabi1224/Programming-Language-Benchmarks/blob/main/bench/algorithm/binarytrees/1.js

$ node 1.js 21
$ top -H -p

v16.14.2:

top - 17:39:12 up 1 day, 22 min,  1 user,  load average: 0.41, 0.50, 0.46
Threads:   7 total,   1 running,   6 sleeping,   0 stopped,   0 zombie
%Cpu(s):  7.0 us,  2.8 sy,  0.0 ni, 90.2 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
MiB Mem :  23818.0 total,    641.0 free,  13632.2 used,   9544.8 buff/cache
MiB Swap:  49152.0 total,  47951.2 free,   1200.8 used.   7510.3 avail Mem 

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND                                                                                                                                     
  92913 ack   20   0 1028048 480700  28820 R  94.3   2.0   0:08.73 node                                                                                                                                        
  92916 ack   20   0 1028048 480700  28820 S   6.0   2.0   0:00.47 node                                                                                                                                        
  92917 ack   20   0 1028048 480700  28820 S   6.0   2.0   0:00.54 node                                                                                                                                        
  92915 ack   20   0 1028048 480700  28820 S   5.0   2.0   0:00.47 node                                                                                                                                        
  92918 ack   20   0 1028048 480700  28820 S   4.3   2.0   0:00.47 node                                                                                                                                        
  92914 ack   20   0 1028048 480700  28820 S   0.0   2.0   0:00.00 node                                                                                                                                        
  92919 ack   20   0 1028048 480700  28820 S   0.0   2.0   0:00.00 node 

v12.18.4:

top - 17:44:01 up 1 day, 27 min,  1 user,  load average: 1.09, 0.65, 0.52
Threads:   7 total,   1 running,   6 sleeping,   0 stopped,   0 zombie
%Cpu(s): 10.4 us,  4.7 sy,  0.0 ni, 84.9 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
MiB Mem :  23818.0 total,   1136.4 free,  13659.7 used,   9021.9 buff/cache
MiB Swap:  49152.0 total,  47892.2 free,   1259.8 used.   7468.0 avail Mem 

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND                                                                                                                                     
  93716 ack   20   0  970844 452148  27948 R  98.7   1.9   0:13.18 node                                                                                                                                        
  93721 ack   20   0  971100 452412  27948 S  22.3   1.9   0:02.42 node                                                                                                                                        
  93719 ack   20   0  970844 452412  27948 S  15.3   1.9   0:01.92 node                                                                                                                                        
  93720 ack   20   0  970844 452412  27948 S  15.3   1.9   0:02.21 node                                                                                                                                        
  93718 ack   20   0  970844 452148  27948 S  15.0   1.9   0:02.07 node                                                                                                                                        
  93717 ack   20   0  970844 452148  27948 S   0.0   1.9   0:00.00 node                                                                                                                                        
  93722 ack   20   0  971100 452412  27948 S   0.0   1.9   0:00.00 node

How often does it reproduce? Is there a required condition?

always

What is the expected behavior?

Can be executed concurrently by multiple threads

What do you see instead?

Only single thread works 100%

Additional information

No response

[gireeshpunathil]

@mr-ackerman - your program is not multi-threaded (does not make use of worker-threads module), so the the concurrency that you are talking about is not real. The code is always run on the main thread. The additional CPU usage you are observing in other threads may be running something else in the runtime (for example gc threads) and their behaviour can potentially change the overall performance of the code too.

[C-Ackerman]

@gireeshpunathil
Thank you, I checked the test results locally. The performance of the v16 version is not as good as that of the v12 when the binarytree is 21 layers, but when the number of binarytree layers is less than 18, the performance of the v16 version is much better than that of the v12. Please what is the reason for this problem

cpu：Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
20.04.1-Ubuntu

[gireeshpunathil]

@mr-ackerman - let me see if I can recreate this behaviour at my end.stay tuned!

[gireeshpunathil]

• I see what you are saying.
• on the other hand, if I remove the console.log statements, the difference goes away!
• can you confirm this behaviour at your end too?

also, what tool / method you are using to measure performance?

[C-Ackerman]

@gireeshpunathil
Yes, console.log does affect performance. I use the stopwatch of the mobile phone to time the execution time of this binarytrees code (because the running time is very long and does not need to be very precise). When using v16.14.2 to run the following code, if there is console.log It took 23s, and it took 13s to delete all console.log. The checksum(longLivedTree) function needs to be executed. In the v12 version, the console.log does not affect the performance. It takes 15s to delete and not delete the console.log

node 1.js 21

/* The Computer Language Benchmarks Game
 * https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
 *
 * contributed by François Pirsch
 * Based on the node.js program from Léo Sarrazin and Andrey Filatkin
 * Remove worker_threads usage by hanabi1224
*/
console.log(process.version)
console.time()


function main() {

    const maxDepth = Math.max(6, +process.argv[2] || 0);
    const stretchDepth = maxDepth + 1;
    const stretchTree = createTree(stretchDepth)
    // console.log(`stretch tree of depth ${stretchDepth}\t check: ${checksum(stretchTree)}`)
    const longLivedTree = createTree(maxDepth);

    for (let depth = 4; depth <= maxDepth; depth += 2) {
        const iterations = 1 << maxDepth - depth + 4;
        let sum = 0;
        for (var i = 0; i < iterations; i++) {
            const tree = createTree(depth)
            sum += checksum(tree)
        }
        // console.log(`${iterations}\t trees of depth ${depth}\t check: ${sum}`)
    }

    console.log(`long lived tree of depth ${maxDepth}\t `);
    checksum(longLivedTree);
    // console.log(
    //     `long lived tree of depth ${maxDepth}\t check: ${checksum(longLivedTree)}`
    // );
    console.log(`--long lived tree of depth ${maxDepth}\t `);
}

function checksum(node) {
    if (!node.left) {
        return 1;
    }
    return 1 + checksum(node.left) + checksum(node.right);
}

function createTree(depth) {
    return depth-- > 0
        ? { left: createTree(depth), right: createTree(depth) }
        : { left: null, right: null };
}

main()

console.timeEnd()

[gireeshpunathil]

thanks @mr-ackerman - with that, I am able to recreate the issue in a smaller test case, showing more than 100% perf degradation.

let t1 = Date.now();
const o = {}
let temp = o
for(var i=0; i < process.argv[2] * 1000000; i++) {
  temp[i] = {}
  temp = temp[i]
}
let t2  = Date.now();
console.log(`time: ${t2 - t1}`)

# n12/node rec 10
time: 2660
# n16/node rec 10
time: 6045

Not sure what is responsible for this, and whether this is expected or documented somewhere.

Will check with v8 team to see what do they recommend. Also let this go back to core.

/cc @nodejs/v8

[camillobruni]

It's not as easy to assess the true performance here.

• process.argv[2] seems like something you want to store in separate variable
• Does the performance diff go away if you don't create a new object here: temp[i] = {};?

If you can, maybe try to run a linux-perf profile to see where we spend time (or --runtime-call-stats)

[C-Ackerman]

@camillobruni
Creating a new object (temp[i] = {};) will affect performance, grab the trace as shown, GC takes up a lot of time

let t1 = Date.now();
const o = {}
const o1 = {}
let temp = o
for(var i=0; i < process.argv[2] * 1000000; i++) {
//   temp[i] = {}
  temp[i] = o1
  temp = temp[i]
}
let t2  = Date.now();
console.log(`time: ${t2 - t1}`)

//v16.14.2
// temp[i] = o1
@:bin$ ./node --trace-event-categories=v8,node,node.async_hooks,node.console,node.environment --trace-event-file-pattern='node-trace-nodeo1.log' test.js 10
time: 576

// temp[i] = {}
@:bin$ ./node --trace-event-categories=v8,node,node.async_hooks,node.console,node.environment --trace-event-file-pattern='node-trace-node.log' test.js 10
time: 5146

v16：

v12：

[camillobruni]

Perfect, could you check that this is still the case in node v17.

[C-Ackerman]

v17.9.0 no difference
test.js

[gireeshpunathil]

looks like there are more gc activities in v16 and v17:

#grep "Mark-sweep" 12 | wc -l
       2
#grep "Mark-sweep" 16 | wc -l
      57
#grep "Mark-sweep" 17 | wc -l
      57
#grep "Scavenge" 12 | wc -l
     132
#grep "Scavenge" 16 | wc -l
     246
#grep "Scavenge" 17 | wc -l
     246
#

wherein the files with numbers are all output of --trace-gc of corresponding runs with matching versions.

• are there changes in sizes in the semi-space and old space between versions?
• are there changes in conditions for kicking in gc (minor/major) between versions?

[C-Ackerman]

@camillobruni
But executing the binarytrees code I modified before, whether or not the console.log is executed, v17 does not perform well.

v17.9.0：

v16.14.2：

v12.18.4：