Closed ElianCordoba closed 1 year ago
MartinJohns
commented
2 years ago Did you actually profile the performance changes? As far as I know the switch is internally compiled to a map, so I would expect absolutely no performance improvements from re-ordering the cases.
ElianCordoba
commented
2 years ago As I mentioned at the end of the post I did bench it but didn't find any major difference. That's why I'm pulling up the PR to test it on a bigger scale to see if there is any improvement outside the noise.
In regards to the switch optimization not yielding more performance I wrote this very simple benchmark that shows some minor improvements.
RyanCavanaugh
commented
2 years ago Super curious to see the perf results. I'm not expecting much because the perf suite doesn't have the sort of enormous files that would be needed to show a significant delta.
RyanCavanaugh
commented
2 years ago The testcase you linked isn't representative at all, since it's using case char === 'a': instead of case 'a':
ElianCordoba
commented
2 years ago Oh wow, that's embarrassing, I coded a little bit too quickly. Here is a more correct benchmark to which I also added two switch true variants
const { Suite } = require('benchmark')
const suite = new Suite;
const data = 'assssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasas'
suite.add('Unoptimized', function () {
for (const char of data) {
switch (char) {
case '0': return;
case '1': return;
case '2': return;
case '3': return;
case 'a': return;
case 's': return;
case 'd': return;
}
}
})
.add('Optimized', function () {
for (const char of data) {
switch (char) {
case 'a': return;
case 's': return;
case 'd': return;
case '0': return;
case '1': return;
case '2': return;
case '3': return;
}
}
})
.add('Switch true', function () {
for (const char of data) {
switch (true) {
case char == 'a': return;
case char == 's': return;
case char == 'd': return;
case char == '0': return;
case char == '1': return;
case char == '2': return;
case char == '3': return;
}
}
})
.add('Switch true strict', function () {
for (const char of data) {
switch (true) {
case char === 'a': return;
case char === 's': return;
case char === 'd': return;
case char === '0': return;
case char === '1': return;
case char === '2': return;
case char === '3': return;
}
}
})
.on('cycle', function (event) {
console.log(String(event.target));
})
.on('complete', function () {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run();
Which yielded the following results
Unoptimized x 18,670,778 ops/sec ±0.45% (99 runs sampled)
Optimized x 105,950,167 ops/sec ±0.12% (101 runs sampled)
Switch true x 110,007,305 ops/sec ±0.07% (98 runs sampled)
Switch true strict x 110,274,698 ops/sec ±0.08% (100 runs sampled)
Fastest is Switch true strictYou're comparing strings, but the scanner uses (hardcoded) numbers in that switch.
MartinJohns
commented
2 years ago In the benchmark code you also return from within the switch, meaning the code will only ever iterate the first character.
But man, benchmarking JavaScript code is hard. I must be missing some hidden optimizations. With the "benchmark" JS library and running node I get vastly different results depending on the order of the tests. There does seem to be a considerable difference in NodeJS, but hardly any in Chrome.
This is the NodeJs code I tested:
const { Suite } = require('benchmark');
const suite = new Suite;
const str = 'assssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasasassssaadaddaassdasdaassaaassaadaaaaassssaasaassasddaaaaasssaadaddaasasas';
const onlyAData = 'a'.repeat(str.length).split('').map(x => x.charCodeAt(0));
const mixedData = str.split('').map(x => x.charCodeAt(0));
suite
.add('Mixed: Check a first', function () {
var a = 0, other = 0;
for (const char of mixedData) {
switch (char) {
case 97: ++a; break;
case 98: ++other; break;
case 99: ++other; break;
case 100: ++other; break;
case 101: ++other; break;
case 102: ++other; break;
case 103: ++other; break;
case 104: ++other; break;
case 105: ++other; break;
case 106: ++other; break;
case 107: ++other; break;
case 108: ++other; break;
case 109: ++other; break;
case 110: ++other; break;
case 111: ++other; break;
case 112: ++other; break;
case 113: ++other; break;
case 114: ++other; break;
case 115: ++other; break;
case 116: ++other; break;
case 117: ++other; break;
case 118: ++other; break;
case 119: ++other; break;
case 120: ++other; break;
case 121: ++other; break;
case 122: ++other; break;
}
}
})
.add('Mixed: Check a last', function () {
var a = 0, other = 0;
for (const char of mixedData) {
switch (char) {
case 98: ++other; break;
case 99: ++other; break;
case 100: ++other; break;
case 101: ++other; break;
case 102: ++other; break;
case 103: ++other; break;
case 104: ++other; break;
case 105: ++other; break;
case 106: ++other; break;
case 107: ++other; break;
case 108: ++other; break;
case 109: ++other; break;
case 110: ++other; break;
case 111: ++other; break;
case 112: ++other; break;
case 113: ++other; break;
case 114: ++other; break;
case 115: ++other; break;
case 116: ++other; break;
case 117: ++other; break;
case 118: ++other; break;
case 119: ++other; break;
case 120: ++other; break;
case 121: ++other; break;
case 122: ++other; break;
case 97: ++a; break;
}
}
})
.add('Only A: Check a first', function () {
var a = 0, other = 0;
for (const char of onlyAData) {
switch (char) {
case 97: ++a; break;
case 98: ++other; break;
case 99: ++other; break;
case 100: ++other; break;
case 101: ++other; break;
case 102: ++other; break;
case 103: ++other; break;
case 104: ++other; break;
case 105: ++other; break;
case 106: ++other; break;
case 107: ++other; break;
case 108: ++other; break;
case 109: ++other; break;
case 110: ++other; break;
case 111: ++other; break;
case 112: ++other; break;
case 113: ++other; break;
case 114: ++other; break;
case 115: ++other; break;
case 116: ++other; break;
case 117: ++other; break;
case 118: ++other; break;
case 119: ++other; break;
case 120: ++other; break;
case 121: ++other; break;
case 122: ++other; break;
}
}
})
.add('Only A: Check a last', function () {
var a = 0, other = 0;
for (const char of onlyAData) {
switch (char) {
case 98: ++other; break;
case 99: ++other; break;
case 100: ++other; break;
case 101: ++other; break;
case 102: ++other; break;
case 103: ++other; break;
case 104: ++other; break;
case 105: ++other; break;
case 106: ++other; break;
case 107: ++other; break;
case 108: ++other; break;
case 109: ++other; break;
case 110: ++other; break;
case 111: ++other; break;
case 112: ++other; break;
case 113: ++other; break;
case 114: ++other; break;
case 115: ++other; break;
case 116: ++other; break;
case 117: ++other; break;
case 118: ++other; break;
case 119: ++other; break;
case 120: ++other; break;
case 121: ++other; break;
case 122: ++other; break;
case 97: ++a; break;
}
}
})
.on('cycle', function (event) {
console.log(String(event.target));
})
.on('complete', function () {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run();And the result:
Mixed: Check a first x 293,276 ops/sec ±0.76% (89 runs sampled)
Mixed: Check a last x 154,734 ops/sec ±1.15% (88 runs sampled)
Only A: Check a first x 565,584 ops/sec ±2.03% (91 runs sampled)
Only A: Check a last x 124,091 ops/sec ±0.55% (90 runs sampled)
Fastest is Only A: Check a firstA browser benchmark seems less drastic of a difference: https://jsben.ch/D9Rk1
But I don't know how reliable this library and the website is.
ElianCordoba
commented
2 years ago @RyanCavanaugh definitely yesterday was a long day 🙃. Today I re-runned that bench property, comparing numbers instead of strings, and I saw a ~1% performance improvement.
Leaving that simple benchmark aside today I created this repo to test both scanner functions, the current version and the one with my changes, they are quite simplified versions but I think it's a fair comparison and a more real to life example. My results show ~5% improvements
@MartinJohns Indeed javascript performance is hard to measure, check that repo I just shared where I was puzzled after getting always the first version of the scanner to run being faster than the second one, it didn't matter wherever was my version or the vanilla one. Then I realized that I had to manually assign undefined to the scan function to kind of free memory or trigger the GC or whatever happens in the back of V8 so that the second run results wouldn't be affected ¯_(ツ)_/¯
🔍 Search Terms
✅ Viability Checklist
My suggestion meets these guidelines:
⭐ Suggestion
While reading the source code of the scanner (mainly the
scanfunction) I noticed that in the switch case to decide what token the current character is going to be could be optimised, since there are many checks in the first positions that would cover very obscure and rarely used characters, for example:The rest of the characters are pretty much never seen
Data to validate the idea
I wrote this simple script that:
These are the results after running that script with the following input:
All charaters frecuency
Letters and digits are compacted
Frequency of letters
25944745524498895Findings
32) is by far the most common spacing character.Optimizations to make
Sort the checks in the order corresponding with the occurrences found. I'm pulling up a PR that I've been working on. Spoiler alert, in my machine I didn't find much of a speedup, but it will be interesting to see the result of your perf suite.