DEV Community: Aurélien Delogu

I benchmarked several queue algorithms

Aurélien Delogu — Mon, 25 Jul 2022 14:15:00 +0000

A few weeks ago I posted a code snippet about an async queue. I wrongly implied that this queue was performant but this was not the case (I mostly said it was performant according to other solutions I analyzed at the time) as stated by @peerreynders.

He came with an algorithm based on swapping arrays so the queue would stay performant without having an O(n) time complexity. I found some other algorithms here and there and I wondered wich solution would be the best one, so I benchmarked them.

To simplify the benchmarking, I dropped all the async handling layer, to focus only on the queue itself.

I tested 4 different algorithms. The related code is available on Github if you want to see the different implementations and the benchmark:

first algo: Array.shift() calls (that's what I used); when dequeuing, we simply call shift() on the item list
second algo: swapping arrays (@peerreynders's solution); it uses two arrays, one for enqueuing items, and one for dequeuing them; when the dequeuing array is empty, the arrays are quickly resized and swapped
third algo: ring array; this code is using two indexes with one array to keep track of its start and end offsets; when dequeuing a delete operation is called on the current index
fourth algo: half size clean up; when reaching the half size of the queue on dequeuing operation, the array is sliced up

If you know other algorithms, please tell me and I'll add it to the benchmarks.

Here's the results:

When enqueuing/dequeuing 1 item:

  queue1.ts is the fastest
   2.89x faster than queue4.ts
   4.73x faster than queue2.ts
   11.67x faster than queue3.ts

For 1000 items:

  queue2.ts is the fastest
   1.17x faster than queue4.ts
   7.18x faster than queue1.ts
   10.21x faster than queue3.ts

For 10 000 items:

  queue2.ts is the fastest
   1.2x faster than queue4.ts
   8.63x faster than queue1.ts
   12.81x faster than queue3.ts

For 100 000 items:

  queue2.ts is the fastest
   1.19x faster than queue4.ts: enqueue/dequeue 100_000 items
   8.26x faster than queue3.ts: enqueue/dequeue 100_000 items
   5523.86x faster than queue1.ts: enqueue/dequeue 100_000 items

The first algorithm is performing better when there's only some elements in the queue. But the performance drastically decreases when reaching a few hundreds of them, and it becomes really critical when reaching thousands of items where enqueuing/dequeuing only one element on a queue of 100 000 items takes 4.5s...

The second algorithm is clearly the winner. But we could optimize things when there's only a few elements in the queue.

The third algorithm is the slower implementation, after the first one. This is because of the delete operation executed at each dequeue() call.

The fourth algorithm is performing well, but can be optimized. Currently, it updates the internal array when reaching the half size of it. It can lead to some performance issues when enqueuing/dequeuing items completely and constantly. To improve that, we could compute dynamically an ideal items count so we slice the array up more often.

To conclude: I need to update my code snippet 😀

Last note: Array.shift() is getting optimized on some platforms, but we shouldn't rely on this to implement algorithms, IMHO.

Credits: Photo by Adrien Delforge on Unsplash

What music genre do you listen to when coding?

Aurélien Delogu — Thu, 14 Jul 2022 05:28:42 +0000

And share with us your favorite track!

For me, I listen to vocals-less music because otherwise it catches my attention to much and keep from think well about my code. My prefered genres so far, depending on the mood: ambient, psybient, psytrance, progressive house, as well as classical music and movie soundtracks.

How to use the contenteditable attribute in Vue 3

Aurélien Delogu — Mon, 11 Jul 2022 14:55:57 +0000

Since I'm unemployed, I'm working on a side project in Vue 3 / TypeScript, so I keep myself up-to-date in frontend development.

Lastly, even if I've 15 years of full-stack experience, I encountered the contenteditable HTML attribute that I didn't know anything about (man there's so much to know in HTML/CSS today).

For those who don't know about it neither, it's an attribute that makes the target tag editable by a simple click: everything is handled natively by the browser itself!

In my application, I had a title that I needed to make editable and I implemented the behaviour by replacing the title by an input when it was clicked. Then I put a v-model attribute on it, and hid the input when the enter button is pressed (and then displayed the title again in place). I already thought when I coded this that it was a bit cumbersome... So I was really intrigued when I met this contenteditable UFO (well, it's not flying per say, but you understood).

I managed to quickly update my code and tested how the thingy worked.

<script setup lang="ts">
  import { ref } from 'vue'

  const title = ref('My title')
  const titleElement = ref(null)

  function validate(event : Event) {
    (event.target as HTMLInputElement).blur()
    title.value = titleElement.value.innerText.trim()
  }

  defineExpose({ titleElement })
</script>

<template>
  <div ref="titleElement" contenteditable spellcheck="false" @keydown.enter="validate">
    {{ title }}
  </div>
</template>

Well... It seems that is all we need 😅🦄

It's clearly better now without the complexity of dealing the edition by ourselves!

Here's the playable snippet if you want to have fun with it!

If you have any questions, don't hesitate to ask them in the comment section 😉

Photo by Thought Catalog on Unsplash

Code snippet: a simple rate limiter

Aurélien Delogu — Fri, 08 Jul 2022 09:44:53 +0000

This code snippet is different from my previous one: A performant async queue. Even if it works quite the same way.

The big difference is that it runs functions after some wait time, instead of waiting some time after functions have finished to run.

There's also an NPM package: dumb-limiter.

Code snippet: How to test and understand DOM events better with this simple HTML snippet

Aurélien Delogu — Fri, 08 Jul 2022 09:14:13 +0000

Because sometimes we don't understand what's going on with DOM events (even more on mobiles), here's an HTML page to test and understand things.

You just have to save it as an HTML file and load it in your browser (by drag-n-droping it for example). At the end of this file there's a list of events that are bypassed to avoid generating a lot of output. You can add/remove events from this list, based on what you want to test. And, of course, you can add/remove HTML tags (just after the <body> tag): add a button, a select, anything you need so you can understand more deeply how DOM events are triggered when interacting with a web page 🦄

Code snippet: A performant async queue

Aurélien Delogu — Fri, 08 Jul 2022 08:51:25 +0000

Here's a queue that handles async functions in order with a wait time between each callback. You can call it from anywhere, all tasks will stay in order and won't overlap each other. It can be used for rate limiting, for example.

There's also an NPM package that has a more complete API: dumb-queue.

Code snippet: How to browse a directory recursively

Aurélien Delogu — Fri, 08 Jul 2022 08:37:08 +0000

Code Snippet: How to avoid calling a function twice until its task has finished

Aurélien Delogu — Fri, 01 Jul 2022 14:20:25 +0000

Fresh is out, neat! But are there other "hybrid" frameworks out there?

Aurélien Delogu — Thu, 30 Jun 2022 09:22:05 +0000

Fresh just came out, and it really reminds me of Phoenix which also handles backend development and also hydrates frontend with reactive components.

Of course, there is SSR in React/Vue/Svelte, and we can also think of Meteor.js but it seems to me that this is not the same intention behind it as those "hybrid" frameworks.

Anyway, do you know any other framework that does server side rendering and handles hydration/reactivity too?

You can cite any framework in any language of course!

How to run a local webserver nowadays

Aurélien Delogu — Tue, 25 Aug 2020 17:21:48 +0000

In the early 2000s, when we wanted to develop our website we generally ended up installing Apache locally with PHP, MySQL, and PhpMyAdmin (hey, I heard someone said "eew!" in the assembly). This setup could take several hours to days, depending on what you wanted to achieve (mostly with Apache's config files).

You could also install EasyPHP or WAMP to save you a lot of time, but these tools always came with counterparts, and nowadays a good app/website should be contained in its own project directory (e.g. git repository).

In 2020 (OMG, am I that old?!), development tools have improved a lot. It is not needed anymore to install a local webserver with a complex configuration. Furthermore, to maximize the same behavior across machines, project's dependencies and resources should be run in isolation and not leak in the system.

Let's see how to achieve it with some of the most trending languages!

The quickest not so dirty way

These different methods will rely on having a static website or internal routing in your application. Any more complex routing/rewriting will, of course, require a real webserver. The same to note if you need to use a database that you cannot mock. These specific needs are handled in the next section.

Also, note that all the following commands are creating a server accessible at http://localhost:8080/ serving the current directory and that I didn't list all possible alternatives from popular frameworks (you should already know how to use them, right?) or any available package to keep this article as short as possible.

I encourage the use of a Makefile (or any other tool like NPM scripts) so you don't have to bother anymore with that "what is the command already?" perpetual question when switching between different projects. For example:

Then, you'll always have the same command to type across your projects: make serve.

For static websites

You can use the http-server NPM package. It's a very powerful web server with support for Gzip, SSL, or catch-all routing. Just install it in your project's dev dependencies and run it with npx http-server.

There are also several other web server libraries like glance or harp.

For Deno projects

You can use the standard file_server lib:

$ deno install -f -allow-net -allow-read file_server https://deno.land/std/http/file_server.ts
$ ~/.deno/bin/file_server -port 8000

For PHP 5.4+ apps

You can use the PHP binary itself with: php -S localhost:8080.

Also: if you don’t have migrated to PHP 7 yet, please do.

For Ruby projects

Starting with 1.9.2, use ruby -run -e httpd . -p 8080.

With older versions, use ruby -rwebrick -e'WEBrick::HTTPServer.new(:Port=>8080,:DocumentRoot=>Dir.pwd).start'.

With Python

Like PHP, Python has also its integrated server!

With Python 2: python -m SimpleHTTPServer 8080.

With Python 3: python3 -m http.server 8080.

With Go language

You can use spark:

$ go get github.com/rif/spark
$ spark -port 8080

In Crystal

We can make use of a standard library:

crystal eval 'require "http/server"; HTTP::Server.new(8000, HTTP::StaticFileHandler.new(".")).listen'

For Rust projects

I did not forget our Rustaceans folks 😉️

$ cargo install https
$ http

You can also use miniserve.

Finally, with Elixir

elixir --no-halt --app inets -e ":inets.start(:httpd,[{:server_name,'s'},{:document_root,'.'},{:server_root,'.'},{:port,8080}])"

The longest and reliable way

Maybe you already know Docker? It's a container management tool vastly used nowadays to ship apps with their underlying stack (like a database, a server, a log manager, etc…).

To test an application locally, creating a Docker image with the same configuration as your production server is clearly the preferred and cleaner way. Having your resources containerized minimizes the side effects of different environments with your project and makes your team happy.

For our example, I won't enter into all the details of the creation of an image, but I created a Github repository with a sample website to show you how it is done. This example covers a docker image with Nginx and PHP7: https://github.com/pyrsmk/docker-nginx-example. But the same principle is easily customizable to Apache and any other language.

For the following, you'll need to install docker on your system. When it's done, you must add your user to the docker group:

$ sudo usermod -aG docker ${USER}
$ su - ${USER}

Now, create an account on DockerHub, and log in to it.

Done? Now let's take a look at what our image looks like.

Here's our Dockerfile:

With the comments, it's pretty straightforward to understand what is going on, but there are several things to note here:

we're using Linux Alpine to build our image because it is small as hell (contrary to Ubuntu) so it builds and runs fast
to better handle services in our image we installed S6-Overlay
we added bash as a dependency for debugging purpose
we're overwriting configuration files directly because it's simpler than processing each file separately; those configuration files are stored in the etc folder on our example repository

The other interesting file is the Makefile (the following example is the concatenation of both Makefiles from the example repository, for simplicity):

The code for the build task seems a bit complicated but it's because we want to automate all other tasks since it's better to set a version number for each image we're building. It's not really needed and this code can be simplified, but why not begin with good practices?

Let's explain a bit what the tasks are doing:

make build: it shows us the current Docker image version and asks us for the new version, then builds it
make publish: it publishes our image on DockerHub, especially useful when working on a team but also to make backups
make bash: really useful when we need to debug when we're working on our image (Dockerfile, configuration files, etc…), it runs bash inside the container
make serve: this is what we're interested in, it runs the image and exposes the inner server to localhost:8080

Note that you shouldn't/won't be able to run the commands from the repository directly as they rely on my own account pyrsmk 😉️

We're done for today!

If you have any questions, do not hesitate to ask as I know that Docker is not easy stuff to step in!

If you're interested to learn more about Docker, there are many useful official resources to read.

You can subscribe to my mailing list.

If you appreciate my work, you may want to support me for the small price of a coffee ☕️ via Ko-fi.