02 May 2025

feedPlanet Lisp

Gábor Melis: Adaptive Hashing

At the 2024 ELS, I gave a talk on adaptive hashing, which focusses on making general purpose hash tables faster and more robust at the same time.

Theory vs Practice

Hash table theory most concerns itself with the asymptotic worst-case cost with a hash function chosen randomly from a family of hash functions. Although these results are very relevant in practice,

There are Perfect Hashing algorithms, that choose an optimal hash function for a given set of keys. The drawback is that they either require the set of keys to be fixed or they are too slow to be used as general purpose hash tables.

Still, the idea that we can do better by adapting the hash function to the actual keys is key. Can we do that online, that is, while the hash table is being used? Potential performance gains come from improving the constant factors mentioned above by

The images above plot regret (the expected number of comparisons of per lookup minus the minimum achievable) and the measured run-time of PUT operations vs the number of keys in the hash table with a particular key distribution. Green is Murmur (a robust hash function), Blue is SBCL's expedient EQ hash. The wiggling of the graphs is due to the resizing of the hash table as keys are added to it.

Note how SBCL's regret starts out much lower and becomes much higher than that of Murmur, but if anything, its advantage grows.

Implementation

The general idea is sound, but turning it into real performance gains is hard due to the cost of choosing a hash function and switching to it. First, we have to make some assumption about the distribution of keys. In fact, default hash functions in language runtimes often make such assumptions to make the common cases faster, usually at the cost of weakened worst-case guarantees.

The rest of this post is about how SBCL's built-in hash tables, which had been reasonably fast, were modified. The core switching mechanism looks at

Adapting EQ hash tables

  1. Init to to constant hash function. This a fancy way of saying that we do linear search in a vector internally. This is an EQ hash table, so key comparison is as single assembly instruction.

  2. When the hash table is grown to more than 32 keys and it must be rehashed anyway, we switch to a hash function that does a single right shift with the number of bits to shift determined from the longest common run of low-bits in the keys.

  3. If too many collisions, we switch to the previous default SBCL EQ-hash function that has been tuned for a long time.

  4. If too many collisions, we switch to Murmur, a general purpose hash. We could also go all the way to cryptographic hashes.

In step 2, the hash function with the single shift fits the memory allocator's behaviour nicely: it is a perfect hash for keys forming arithmetic sequences, which is often approximately true for objects of the same type allocated in a loop.

adaptive-hash-eq-put

In this figure, the red line is the adaptive hash.

Adapting EQUAL hash tables

For composite keys, running the hash function is the main cost. Adaptive hashing does the following.

adaptive-hash-string-put


So, SBCL hash tables have been adaptive for almost a year now, gaining some speed in common cases, and robustness in others.

The full paper is here.

adaptive-hashing

02 May 2025 12:00am GMT

01 May 2025

feedPlanet Lisp

Joe Marshall: It Still Sucks

Don't get me wrong. I"m not saying that the alternatives are any better or even any different.

Unix has been around more than forty years and it is still susceptible to I/O deadlock when you try to run a subprocess and stream input to it and output from it. The processes run just fine for a while, then they hang indefinitely waiting for input and output from some buffer to synchronize.

I'm trying to store data in a database. There aren't any good database bindings I could find, so I wrote a small program that reads a record from stdin and writes it to the database. I launch this program from Common Lisp and write records to the input of the program. It works for about twenty records and then hangs. I've tried to be careful to flush and drain all streams from both ends, to no avail.

I have a workaround: start the program, write one record, and quit the program. This doesn't hang and reliably writes a record to the database, but it isn't fast and it is constantly initializing and creating a database connection and tearing it back down for each record.

You'd think that subprocesses communicating via stream of characters would be simple.

01 May 2025 12:29pm GMT

30 Apr 2025

feedPlanet Lisp

Neil Munro: Ningle Tutorial 6: Database Connections

Contents

Introduction

Welcome back, in this tutorial we will begin looking at how to work with SQL databases, specifically SQLite3, MySQL, and PostgreSQL. We will be using the mito ORM to create user models and save them to the database using the form we created previously. Mito itself is a basic ORM and includes several mixins to provide additional functionality, we will use one called mito-auth to provide password hashing and salting.

It is important to know that mito is based on top of a SQL library known as SXQL, we will occasionally use SXQL to write queries with mito, while it's not always required to use SXQL, there are times where it will make life easier. To achieve this, I elected to :use SXQL in my package definition.

(defpackage ningle-tutorial-project
  (:use :cl :sxql)

Part of working with databases using an ORM is creating the initial database/tables and managing changes over time, called migrations, mito appears to have a migrations system, although I was unable to get it working, but I developed a means by which to apply migrations, so perhaps in a future tutorial the subject can be revisited. As such, in addition to seeing how to connect to the respective SQL databases, we will write implementation specific migration functions.

We will follow the example of setting up a secure user registration system across all three SQL implementations. One thing to bear in mind is that it is beyond the scope of this tutorial to instruct how to setup MySQL or PostgreSQL, I would recommend learning how to set them up using docker. All that having been said, let's have a look at the different databases and how to connect to them!

Please bear in mind that when working with SQLite remember to add .db to your .gitignore as you most certainly don't want to accidentally commit a database into git! SQLite, being a file based database (unlike MySQL and PostgreSQL) will create a file that represents your database so this step only applies to SQLite.

Installing Packages

To begin with we will need to ensure we have installed and added the packages we need to our project asd file, there are three that we will be installing:

As normal you will need to add them in the :depends-on section. Please note however that there is an issue in mito-auth that prevents it from working in MySQL, I have submitted a fix but it has not been merged yet, so for now you can use my branch, if you do, please ensure you check it out via git into your quicklisp/local-projects directory.

:depends-on (:clack
             :cl-dotenv
             :djula
             :cl-forms
             :cl-forms.djula
             :cl-forms.ningle
             :ingle
             :mito
             :mito-auth
             :ningle)

Mito is a package for managing models/tables in our application, mito-auth is a mixin that enables models to have a secure password field, not all models will need this, but our user model will! ingle is a small library that includes some very useful utilities, one of which is a redirect function which will be very useful indeed!

Now that that is done, we must set up the middleware, you might remember from Part 3 that middleware is placed in the lack.builder:builder function call in our start function.

SQL Middleware

Mito provides middleware to establish and manage database connections for SQLite3, MySQL, and PostgreSQL, when you build your solution you will need to pick a database implementation, for production systems I suggest PostgreSQL, but if you are just starting out, you can use SQLite.

SQLite3

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (djula:set-static-url "/public/")
    (clack:clackup
      (lack.builder:builder
       :session
       `(:mito
         (:sqlite3
          :database-name ,(uiop:getenv "SQLITE_DB_NAME")))
       (:static
        :root (asdf:system-relative-pathname :ningle-tutorial-project "src/static/")
        :path "/public/")
       *app*)
     :server server
     :address address
     :port port))

MySQL

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (djula:set-static-url "/public/")
    (clack:clackup
      (lack.builder:builder
       :session
       `(:mito
         (:mysql
          :database-name ,(uiop:native-namestring (uiop:parse-unix-namestring (uiop:getenv "MYSQL_DB_NAME")))
          :username ,(uiop:getenv "MYSQL_USER")
          :password ,(uiop:getenv "MYSQL_PASSWORD")
          :host ,(uiop:getenv "MYSQL_ADDRESS")
          :port ,(parse-integer (uiop:getenv "MYSQL_PORT"))))
       (:static
        :root (asdf:system-relative-pathname :ningle-tutorial-project "src/static/")
        :path "/public/")
       *app*)
     :server server
     :address address
     :port port))

PostgreSQL

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (djula:set-static-url "/public/")
    (clack:clackup
      (lack.builder:builder
       :session
       `(:mito
         (:postgres
          :database-name ,(uiop:native-namestring (uiop:parse-unix-namestring (uiop:getenv "POSTGRES_DB_NAME")))
          :username ,(uiop:getenv "POSTGRES_USER")
          :password ,(uiop:getenv "POSTGRES_PASSWORD")
          :host ,(uiop:getenv "POSTGRES_ADDRESS")
          :port ,(parse-integer (uiop:getenv "POSTGRES_PORT"))))
       (:static
        :root (asdf:system-relative-pathname :ningle-tutorial-project "src/static/")
        :path "/public/")
       *app*)
     :server server
     :address address
     :port port))

Testing The Connection

Before we go further with building models and migration functions, we should test that the connections work and the most basic of SQL statements. We will be working on our register controller, so that seems like as good a place as any to place a simple check.

(setf (ningle:route *app* "/register" :method '(:GET :POST))
    (lambda (params)
        (let ((query (mito:retrieve-by-sql "SELECT 2 + 3 AS result")))
            (format t "Test: ~A~%" query))

        (let ((form (cl-forms:find-form 'register)))
        ...

Here, in the controller we have added a small (temporary) check to ensure that the database connections are set up correctly, when you run the application and perform a GET request on this route, you should see the output printed in the console for:

Test: ((RESULT 5))

It might look a little odd, but rest assured that this is proof that everything is right and the connection works! We will be removing this later as it serves just as a small check. So with that done, we can begin to look into writing our first model, our user model.

Creating Models

Models are a way to represent both a generic object, and any specific object of that type in a relational database system. For example you might have a Book model, that represents a book table, however a book is just a way to classify something any doesn't tell you anything specific about any individual book. So here we will create a User model, that refers to all users, but each instance of a User will contain the specific information about any given user.

We will create a new file called models.lisp:

(defpackage ningle-tutorial-project/models
  (:use :cl :mito)
  (:export #:user))

(in-package ningle-tutorial-project/models)

(deftable user (mito-auth:has-secure-password)
  ((email    :col-type (:varchar 255) :initarg :email    :accessor email)
   (username :col-type (:varchar 255) :initarg :username :accessor username))
  (:unique-keys email username))

Now, mito provides a deftable macro that hides some of the complexities, there is a way to use a regular class and change the metaclass, but it's much less typing and makes the code look nicer to use the deftable syntax. It is important to note however that we use the mixin from mito-auth called has-secure-password. Obviously this mixin wouldn't be needed in all of our models, but because we are creating a user that will log into our system, we need to ensure we are handling passwords securely.

Writing Migrations

Now that we have this we need to write the migration code I mentioned earlier, databases (and their models) change over time as application requirements change, as columns get added, removed, changed, etc it can be tricky to get right and you certainly would prefer to have these done automatically, a stray SQL query in the wrong connected database can do incredible damage (trust me, I know!), so migrations allow us to track these changes and have the database system manage them for us.

This code will set up connections to the implementation we want to use and delegate migrations to mito, so pick your implementation and place it in migrations.lisp.

SQLite3

(defpackage ningle-tutorial-project/migrations
  (:use :cl :mito)
  (:export #:migrate))

(in-package :ningle-tutorial-project/migrations)

(defun migrate ()
  "Explicitly apply migrations when called."
  (dotenv:load-env (asdf:system-relative-pathname :ningle-tutorial-project ".env"))
  (format t "Applying migrations...~%")
  (mito:connect-toplevel
    :sqlite3
    :database-name (uiop:native-namestring (uiop:parse-unix-namestring (uiop:getenv "SQLITE_DB_NAME"))))
  (mito:ensure-table-exists 'ningle-tutorial-project/models:user)
  (mito:migrate-table 'ningle-tutorial-project/models:user)
  (mito:disconnect-toplevel)
  (format t "Migrations complete.~%"))

MySql

(defpackage ningle-tutorial-project/migrations
  (:use :cl :mito)
  (:export #:migrate))

(in-package :ningle-tutorial-project/migrations)

(defun migrate ()
  "Explicitly apply migrations when called."
  (dotenv:load-env (asdf:system-relative-pathname :ningle-tutorial-project ".env"))
  (format t "Applying migrations...~%")
  (mito:connect-toplevel
    :mysql
    :database-name (uiop:native-namestring (uiop:parse-unix-namestring (uiop:getenv "MYSQL_DB_NAME")))
    :username (uiop:getenv "MYSQL_USER")
    :password (uiop:getenv "MYSQL_PASSWORD")
    :host (uiop:getenv "MYSQL_ADDRESS")
    :port (parse-integer (uiop:getenv "MYSQL_PORT")))
  (mito:ensure-table-exists 'ningle-tutorial-project/models:user)
  (mito:migrate-table 'ningle-tutorial-project/models:user)
  (mito:disconnect-toplevel)
  (format t "Migrations complete.~%"))

PostgreSQL

(defpackage ningle-tutorial-project/migrations
  (:use :cl :mito)
  (:export #:migrate))

(in-package :ningle-tutorial-project/migrations)

(defun migrate ()
  "Explicitly apply migrations when called."
  (dotenv:load-env (asdf:system-relative-pathname :ningle-tutorial-project ".env"))
  (format t "Applying migrations...~%")
  (mito:connect-toplevel
    :postgres
    :database-name (uiop:getenv "POSTGRES_DB_NAME")
    :host (uiop:getenv "POSTGRES_ADDRESS")
    :port (parse-integer (uiop:getenv "POSTGRES_PORT"))
    :username (uiop:getenv "POSTGRES_USER")
    :password (uiop:getenv "POSTGRES_PASSWORD"))
  (mito:ensure-table-exists 'ningle-tutorial-project/models:user)
  (mito:migrate-table 'ningle-tutorial-project/models:user)
  (mito:disconnect-toplevel)
  (format t "Migrations complete.~%"))

It will be necessary to add these two files into the :components section of your project asd file.

  :components ((:module "src"
                :components
                ((:file "models")
                 (:file "migrations")
                 (:file "forms")
                 (:file "main"))))

Just remember if you are using MySQL or PostgreSQL, you will need to ensure that the database you want to connect to exists (in our case ntp), and that your connecting user has the correct permissions!

Running Migrations

Now that everything is set up, we will need to perform our initial migrations:

(ningle-tutorial-project/migrations:migrate)

If this has worked, you will see a lot of output SQL statements, it's quite verbose, however this only means that it is working and we can move onto actually creating and saving models.

Removing Connection Check

Now that we have migrations and models working we should remember to remove this verification code that we wrote earlier.

(let ((query (mito:retrieve-by-sql "SELECT 2 + 3 AS result")))
    (format t "Test: ~A~%" query))

Registering & Querying Users

What we are going to do now is use the user register form and connect it to our database, because we are registering users we will have to do some checks to ensure since we stated that usernames and email addresses are unique, we might want to raise an error.

(when valid
    (cl-forms:with-form-field-values (email username password password-verify) form
        (when (mito:select-dao 'ningle-tutorial-project/models:user
                                 (where (:or (:= :username username)
                                             (:= :email email))))
                            (error "Either username or email is already registered"))

We can see from this snippet here that mito uses the SXQL Domain Specific Language for expressing SQL statements. Using the select-dao we can query the user table and apply where clauses using a more Lispy like syntax to check to see if an account with the username or email already exists. Such DSLs are common when interacting with SQL inside another programming language, but it's good to know that from what we learned earlier that it can handle arbitrary SQL strings or this more Lispy syntax, so you can use pure SQL syntax, if necessary.

While having this check isn't necessary, it does make the error handling somewhat nicer, as well as exploring parts of the mito api. We will also add a check to raise an error if the passwords submitted in the form do not match each other.

(when (string/= password password-verify)
    (error "Passwords do not match"))

If both of these pass (and you can test different permutations of course), we can continue to using mito to create our first user object!

(mito:create-dao 'ningle-tutorial-project/models:user
                                           :email email
                                           :username username
                                           :password password)

The final thing to add is that we should redirect to another route, which we can do with the ingle:redirect function.

(ingle:redirect "/people")

You will notice that we are redirecting to a route that doesn't (yet) exist, we will write the controller below after we have finished this controller, the multiple-value-bind section of which, when completed, looks like this:

(multiple-value-bind (valid errors)
        (cl-forms:validate-form form)
    (when errors
        (format t "Errors: ~A~%" errors))

    (when valid
        (cl-forms:with-form-field-values (email username password password-verify) form
            (when (mito:select-dao 'ningle-tutorial-project/models:user
                    (where (:or (:= :username username)
                                (:= :email email))))
                (error "Either username or email is already registered"))

            (when (string/= password password-verify)
                (error "Passwords do not match"))

            (mito:create-dao 'ningle-tutorial-project/models:user
                :email email
                :username username
                :password password)
        (ingle:redirect "/people"))))

Getting All Users

We will look at two final examples of using mito before we finish this tutoral, as mentioned earlier we will write a new /people controller, which will list all the users registered in the system, and we will create a /people/:person controller to show the details of an individual user.

Starting with the /people controller, we create a controller like we have seen before, we then use a let binding to store the result of (mito:retrieve-dao 'ningle-tutoral-project/model:user), this is how we would get all rows from a table represented by the class 'ningle-tutorial-project/models:user. We then pass the results into a template.

(setf (ningle:route *app* "/people")
      (lambda (params)
        (let ((users (mito:retrieve-dao 'ningle-tutorial-project/models:user)))
          (djula:render-template* "people.html" nil :title "People" :users users))))

The html for this is written as such:

{% extends "base.html" %}

{% block content %}
<div class="container">
    <div class="row"    >
        <div class="col-12">
            {% for user in users %}
                <div class="row mb-4">
                    <div class="col">
                        <div class="card">
                            <div class="card-body">
                                <h5 class="card-title"><a href="/people/{{ user.username }}">{{ user.username }}</a></h5>
                                <p class="card-text"><a href="/people/{{ user.email }}">{{ user.email }}</a></p>
                                <p class="text-muted small"></p>
                            </div>
                        </div>
                    </div>
                </div>
            {% endfor %}
            {% if not users %}
                <div class="row">
                    <div class="col text-center">
                        <p class="text-muted">No users to display.</p>
                    </div>
                </div>
            {% endif %}
        </div>
    </div>
</div>
{% endblock %}

Getting A Single User

In our individual person view, we see how a route may have variable data, our :person component of the URL string, this will be either a username or email, it doesn't really matter which as we can have a SQL query that will find a record that will match the :person string with either the username or email. We also take advantage of another ingle function, the get-param, which will get the value out of :person. We use a let* binding to store the user derived from :person and the result of mito:select-dao (using the person), we then pass the user object into a template.

As we saw before this query was used to check for the existence of a username or email address in our register controller.

(setf (ningle:route *app* "/people/:person")
      (lambda (params)
        (let* ((person (ingle:get-param :person params))
               (user (first (mito:select-dao
                              'ningle-tutorial-project/models:user
                              (where (:or (:= :username person)
                                          (:= :email person)))))))
          (djula:render-template* "person.html" nil :title "Person" :user user))))

And here is the template for an individual user.

{% extends "base.html" %}

{% block content %}
<div class="container">
    <div class="row">
        <div class="col-12">
            <div class="row mb-4">
                <div class="col">
                    {% if not user %}
                        <h1>No users</h1>
                    {% else %}
                        <div class="card">
                            <div class="card-body">
                                <h5 class="card-title">{{ user.username }}</h5>
                                <p class="card-text">{{ user.email }}</p>
                                <p class="text-muted small"></p>
                            </div>
                        </div>
                    {% endif %}
                </div>
            </div>
        </div>
    </div>
</div>
{% endblock %}

Conclusion

This was a rather large chapter and we covered a lot, looking at the different means by which to connect to a SQL database, defining models, running migrations and executing queries, of course we are just getting started but this is a massive step forward and our application is beginning to take shape. I certainly hope you have enjoyed it and found it useful!

To recap, after working your way though this tutorial you should be able to:

Github

Resources

30 Apr 2025 9:30pm GMT