Parsing Millions of URLs per Second

Hello. Today I'm going to talk about parsing millions of URLs per second. My name is Elzen Zipli and I'm a senior software engineer at Sentry. I'm an OGS technical steering committee member. I'm an OpenJS foundation cross-project council member. You can reach me from my GitHub account, github.com, and from X, formerly known as Twitter, from X.com.

Software performance in the last decade has changed drastically. The main goal was to reduce cost in cloud environments such as AWS, Azure or Google Cloud. The latency has been a problem, and in order to improve it, we need to optimize our code more than ever right now. Reduce complexity, parallelism, caching, and performance brings those kinds of things. And most importantly, the climate change. Faster computers resulted in better tomorrows and better climate.

So state of Node.js performance 2023. This is a quote from that. Since Node.js 18, a new URL parsing dependency was added to Node.js 8. This addition bumps the Node.js performance from parsing URLs to a new level. Some results could reach up to an improvement of 400%. State of Node.js performance 2023 and this is written by Rafael Gonzaga, which is a Node.js technical steering committee member. This talk is about how we reach 400% improvement in URL parsing. Another quote from James Snell from Cloudflare and also Node.js TSC. Just set a benchmark for a code change, go from 11 seconds to complete down to about half a second to complete, this makes me very happy. This is in reference to adding Ada URL to Cloudflare.

So let's start with the structure of a URL. For example, there is HTTPS user pass at example.com, 1 2 3 4, which is the port number, then we have Foo, Bar, Buzz, and QUU. So it starts with the protocol, HTTPS is the protocol, it ends with the slash. Then we have the username and password. This is an optional field in all URLs. Then we have the host name, which is example.com. Then we have the port, which is 1 2 3 4. And then we have the path name, which is slash Foo slash Bar.

And then we see the search, which starts with a question mark Buzz. And then we have the hash, which is QUU. So port number, path name, search, hash, username, password, they're all optional. Even host name is optional if you have a file URL. But this is just an example about how this structure of a URL is. There are also, despite the structure of the URL, there is also different encodings that the URL specification supports, such as non-ASCII format, which is the first one. Then we support file-based URLs, which is what you see in Unix-based systems, file, slash, slash, slash, Foo, Bar, Buzz, Foo, Bar, Test, Node.js. Then we have JavaScript URLs, which is JavaScript colon alert. Then we have percent encoding that starts with a URL that has subsections, sub strings that has a percentage character in dash. And then we have path names with dots, which is like example.org slash dot A slash A dot dot slash B, which basically resolves into a different URL according to the URL specification. Then we have IPv4 addresses with hex and octal digits, 127.0.0.0.0.0.0.0.1, which is 127.0.0.0.1. And we have also IPv6 and so on and so forth. According to what we do URL, if we put in this input string, HTTPS711home dot dot slash Montreal. PHP in PHP, it's unchanged. In Python, it's unchanged. In what we do URL, which is implemented by Chrome, Safari and all the browsers, including Ada, it's xn dash dash 711 and so on so forth. In curl, it's a lot different. And as you see, in Go runtime, it's a lot different as well. This is mostly because of different implementations and also from all other subsystems, all other languages doesn't follow the what we do URL strictly. For PHP and Python, they basically parse the URL from start and string without any making allocations. And for curl and Go, they implement a different specification called RFC 3787. Or similar, I'm not really quite sure about. So we have these old assumptions like does URL parsing really matter? Is it the bottleneck to some performance metric? URLs are free, you don't gain anything by overlaying. This is what, these were the assumptions that we broke with our work. And you will see why.

So let's create, let's, let's understand if these assumptions are true. Let's create the HTTP benchmark using Festify. And there are two endpoints that you get from using a post, which is slash simple. It basically has a URL in the JSON body and the other one as well. But in the first one, we are not returning, we are returning the URL without doing anything. In the second one, we are parsing it with new URL. And then we are returning the href, which is the string that corresponds to it. And then at the bottom, you will see the example input that we sent and the comparison between them.

In slash simple, we almost have 60,000 requests per second. But if we parse it, we have around 50,000, 50, 52, maybe 52,000. So URL parsing was a battle bottleneck in node 18.50. So this is actually run on node 18.50, before ADA, before any optimizations that are done in URL parsing.

So announcing ADA URL parser, it's named after my daughter's, Ada Nisiply. It's a full what-vg URL supported parser. There is no dependency, full portability. This means that this it doesn't include ICU. It's over 20,000 lines of code. It's a six month's work of 25 contributors. It's Apache 2.0 and MIT license. It's available at github.com. It's right now used by Node.js and CloudFlare workers.

Overall, it can parse 6 million URLs per second. This benchmark that I'm sharing with you right now is run on Apple M2, LLVM 14. It has a wide range of realistic data sources. And it's faster than alternatives in C, C++ and ROS. And for libraries that implements what-vg URL, it's a lot faster as well. So on the right side, you will see Wikipedia 100k, which is 100,000 URLs parsed and analyzed from the Wikipedia domain. Top 100 is the most traffic getting websites in the world. And the third one is Linux files. Basically we crawl the Linux operating system and stored every path. Then we have user base and the HTTP that we found from the internet. As you can see, Ada is almost twice as fast from the second alternative. It's around 6 to 7% faster than curl right now. So in order to do that, we have some tricks that in general will give you an idea about how we achieve these amazing results.

Trick one is perfect hashing. This means that we reduced the number of branches. And if you can see we have names of an array of string view, HTTP, HTTPS, W, FTP, WSS file. Then we have these contexts called HTTP, not special URLs, HTTPS, WS, which corresponds to web sockets, FTP, WSS and file. These types correspond to what-vg URL scheme types. And in order to get the scheme type from here, we used an algorithm to perfectly hash, perfectly find the correct position inside the names array of the input that we have. And this is one of the examples.

The second trick is of course memoization tables. In order to reduce the number of branches and reduce if statements, what we did was that we used bitwise operations as well as getting the already parsed values from a table itself. By doing that, we have an is bad charge table that contains of 255 characters and it stores zero or one according to if it's a bad character or not. This is a really great example about improving the performance of a function and within the cost of increasing the size of the binary as well.

The third one is use vectorization. So do not process byte by byte when you can process 16 by 16. New processors in the world right now support 16 by 16 vectorization iteration through the array, so we don't need to iterate one by one. And for example, this example has tabs or a new line. In order to understand if a particular string has a tab or a new line character, we use the following example. I'm not going to dive into this for the sake of today, but the information is out there and there are optimizations available to increase the iteration and execution time of a basic for loop with such certain tricks. So on top of these efficient C++ JavaScript bridge, these optimizations, we provided an efficient bridge between the JavaScript and the C++ implementation. This is done particularly for Node.js integration so that the serialization costs the string to string conversion from C++ to JavaScript is reduced as much as possible. So passing multiple strings is expensive, and pass one string with offset. So basically we have an href and we return eight different integers that correspond to protocol end, username end, host start, host end and so on and so forth. If we know protocol end, then you can take the substring of the href by taking zero to protocol end for example, and if you have a username and so on and so forth. This is kind of the optimizations that improves the code base by 60, 70, 80 percent.

Here's an example JavaScript benchmark. It basically takes lines and it tries to parse it and it adds the length of the href to a value and then it counts the good URLs and the bad URLs. This is done to eliminate just JITs compiler optimization so that that code to disable that code elimination in V8. The benchmark is available at github.com slash adurl slash gs url benchmark and please take a look at it and if there's something that we missed, please take the time to create an issue on the GitHub repository. This particular benchmark on node 18.15.0 ran around 0.8 million URLs per second. At that time dno 1.32.5 was doing 0.9 million, bun 0.5.9 was around 1.5 million, and on node 20.1.0, it's right now 2.9 million URLs per second. The Ada C++ library is safe and efficient.

We wrote it in modern C++. We tested extensively. We tested with sanitizers. We did fuzzing testing. We have lots of unit tests which particularly contributed to web platform tests as well.

A few minor bugs were reported in the past couple of months, mostly related to the standard. We quickly fixed under 24 hours.

Ada is available in the language of your choice. In JavaScript, it's available in Node.js. We have C bindings at GitHub. We have Rust, Go, Python, and R. Often, this is the only way to get support in those particular languages.

Thank you for listening. You can reach out to Ada URL from Ada URL.com. You can reach out to my blog at and you can reach out to my co-author, Daniel Lemire's blog from lemire.me. Thank you.