Performance improvements

[cfvescovo]

@j-mendez and I have had a discussion about what should be done to improve processing speeds for the select operation.
We think that, as we are aiming for maximum performance, the following could be useful:

• some benchmarks (to run on Github Actions too to check for regressions)
• code profiling

@j-mendez also proposed testing some variations of our code he's been using in production since they made a difference for intense workloads.

Also, huge thanks to @adamreichold!

[adamreichold]

Yes, benchmarks would certainly be nice. Either using the built-in #[feature(test)] benchmarks and a nightly toolchain. Or a stable variant like Criterion.

To focus the benchmarks I would suggest we start by collecting some typical HTML documents and putting them into version control as a stable base for comparisons.

The we should probably benchmark at least Html::parse_document on those. And then running some selectors, ideally a somewhat varied set based tag names, attributes, identifiers, classes, etc, against the different documents as well.

I am not sure about running them in a noisy environment like GitHub Actions but just having them in the repository and ready to run should make this step trivial in any case.

[j-mendez]

I think that is a very good starting place. For balancing the test cases it would be nice to get 3 different range sizes.

It could be beneficially to be able to take different paths depending on pre-assumption knowledge on the node length / size if the benchmarks show some potential room for improvements.

Currently I am using this library concurrently and I was able to profile a bottleneck towards the full select. For my situation spawning thousands of tasks at a time. The performance starts to slow down as the tasks or load is increasing and at a certain point the select would take over 1ms-10ms etc which would cause some drops in packets not being able to switch to the current active task.

This lead me to pulling out the select at first so I could just perform the method I would need inside the iteration of the original select ( this helped ). I realized regardless of the sync improvements the fact of reaching 1ms would throw away a big concurrency factor and looked further into the code and saw I could open up the tree and walk through it async with atom tendrils.

Processing it in this fashion starts off a bit slower but, as the concurrency limits increase it drastically outperforms the sync methods.

-- To our benchmarks

After we get to a good point on the concrete areas like Html::parse_document a benchmark that spawns 0..300 tasks on the tokio runtime and 0..100 std threads could help measure this.

Starting with parse_document is a good area to first enter benchmarks since it takes a bit a time to process. After getting the atomic tendrils being able to yield to the system after parse_document helped out a lot. I wonder if it could benefit from an async implementation as well? ( I have not looked at that part of the code yet).

Thank you for getting this discussion started @cfvescovo . @adamreichold very impressive stuff on your end, great work.

[cfvescovo]

I am not sure about running them in a noisy environment like GitHub Actions

It could be beneficial if our aim is to check for regressions. From experience, benchmarks run as Github Actions should have a 10% - 20% amplitude so we would still be able to detect (big) potential regressions introduced by PRs.

I agree fine-tuning to detect small differences should be performed locally though.

Note to self: CI minutes are limited. We should be cautious.

[adamreichold]

After we get to a good point on the concrete areas like Html::parse_document a benchmark that spawns 0..300 tasks on the tokio runtime and 0..100 std threads could help measure this.

To be honest, I think we should start simpler: With micro benchmarks targeting the algorithmic efficiency of the crate. Large scale benchmarks involving tasks/threads are significantly harder to make reproducible and consistent.

I wonder if it could benefit from an async implementation as well? ( I have not looked at that part of the code yet).

I am sceptical to make this purely computational code async as this is generally only worsens its throughput. If this taking too long and blocks your worker threads from handling incoming traffic, maybe putting the parsing into spawn_blocking would be the better solution.