Just because I don't care doesn't mean I don't understand.
698 stories
·
3 followers

Python⇒Speed: 6× faster binary search: from compiled code to mechanical sympathy

1 Comment

How do you speed up computational Python code? A common, and useful, starting point is:

  1. Pick a good algorithm.
  2. Use a compiled language to write a Python extension.
  3. Maybe add parallelism so you can use multiple CPU cores.

But what if you need more speed? Consider the following real problem, one of the steps in scikit-learn’s gradient histogram boosting algorithm:

  • You have a large array of floating point numbers.
  • You want to assign them to the integer range 0-254, spread out evenly.

scikit-learn implements this by splitting up the full range of float values into 255 buckets, creating a sorted array of bucket boundaries, and then using binary search to choose the appropriate bucket for each value. The binary search is implemented in a compiled language, and it can run in parallel on multiple cores.

Recently, as part of my work at Quansight, and inspired by two posts by Paul Khuong, I sped up this implementation significantly. How? By making sure the code wasn’t fighting against the CPU.

In this article I’m going to walk you through that speed-up, demonstrated on a simplified example. Then I’m going to demonstrate a series of additional optimizations, with the final version running 6× faster than the original one.

It’s worth knowing that I will be speeding through mentions of many different low-level hardware topics: instruction-level parallelism, branch (mis)prediction, memory caches, SIMD, and more. This is only one article, it can only briefly introduce you to what’s possible, it can’t function as an in-depth tutorial. So I’ll talk about how you can learn more about these topics at the end of the article.

Read more...
Read the whole story
jgbishop
3 hours ago
reply
Pretty cool performance boosts.
Raleigh, NC
Share this story
Delete

Pickles - 2026-06-30

1 Comment
Read the whole story
jgbishop
11 days ago
reply
Haha!
Raleigh, NC
Share this story
Delete

Ferrari reveals its first EV, with design help from Jony Ive

1 Comment and 2 Shares
An image of a blue Ferrari with a minimalist design and black accents.
The Ferrari Luce will start at €550,000 in Italy, but US pricing hasn’t been announced. | Image: Ferrari

After months of teasers, Ferrari is offering the first full view of its Luce electric vehicle. The Luce is notable not just for being Ferrari's first EV, but for being designed in collaboration with Jony Ive and Mark Newson at their collective LoveFrom. It's also going to be Ferrari's second four-door car and its first five-seat one.

We already knew Ive and Newson were working on the Luce's interiors, which were shown off earlier this year. Now Ferrari says LoveFrom was allowed to "define the design direction of the project from the outset," inside and out.

Tim Stevens reporting for Engadget offers a few firsthand impression …

Read the full story at The Verge.

Read the whole story
jgbishop
47 days ago
reply
This thing is *ugly*...
Raleigh, NC
Share this story
Delete

Brevity - 2026-04-30

1 Comment
Read the whole story
jgbishop
72 days ago
reply
What a deep cut reference!
Raleigh, NC
Share this story
Delete

Django: fixing a memory “leak” from Python 3.14’s incremental garbage collection

1 Comment

Back in February, I encountered an out-of-memory error while migrating a client project to Python 3.14. The issue occurred when running Django’s database migration command (migrate) on a limited-resource server, and seemed to be caused by the new incremental garbage collection algorithm in Python 3.14.

At the time, I wrote a workaround and started on this blog post, but other tasks took priority and I never got around to finishing it. But four days ago, Hugo van Kemenade, the Python 3.14 release manager, announced that the new garbage collection algorithm will be reverted in Python 3.14.5, and the next Python 3.15 alpha release, due to reports of increased memory usage.

Here’s the story of my workaround, as extra evidence that reverting incremental garbage collection is a good call.

Python 3.14’s incremental garbage collection

Python (well, CPython) has a garbage collector that runs regularly to clean up unreferenced objects. Most objects are cleaned up immediately when their reference count drops to zero, but some objects can be part of reference cycles, where some set of objects reference each other and thus never reach a reference count of zero. The garbage collector sweeps through all objects to find and clean up these cycles.

Python 3.14 changed garbage collection to operate incrementally. Previously, a garbage collection run would sweep through all objects in one go, but this could lead to “stop the world” stalls where your program’s real work could pause for seconds while the garbage collector did its job. The incremental garbage collection algorithm instead does a fraction of the work at a time, spreading out the cost of garbage collection.

Here’s the full release note (historical source):

Incremental garbage collection

The cycle garbage collector is now incremental. This means that maximum pause times are reduced by an order of magnitude or more for larger heaps.

There are now only two generations: young and old. When gc.collect() is not called directly, the GC is invoked a little less frequently. When invoked, it collects the young generation and an increment of the old generation, instead of collecting one or more generations.

The behavior of gc.collect() changes slightly:

  • gc.collect(1): Performs an increment of garbage collection, rather than collecting generation 1.
  • Other calls to gc.collect() are unchanged.

(Contributed by Mark Shannon in 108362.)

The problem

I’d been helping one of my clients upgrade to Python 3.14 for a few months, chipping away at compatibility work like upgrading dependencies and fixing deprecations. Tests were finally all passing and everything was working on the local development server. The next stop was to launch a temporary deployment using Python 3.14 via Heroku’s review apps feature.

At the basic tier, Heroku review apps use fairly resource-constrained servers, including just 512MB of RAM, with the ability to temporarily burst up to nearly 1GB (200%). Paying for larger servers is an option, but unfortunately the next step up is pretty expensive.

When I launched a review app for my Python 3.14 branch, I found its release phase failed while running migrate. Inspecting the logs, I found the migrations started fine:

$ heroku logs --app example-python-314-wsgk3w --num 1000 | less
...
app[release.6634]: System check identified no issues (26 silenced).
app[release.6634]: Operations to perform:
app[release.6634]: Apply all migrations: admin, auth, contenttypes, ...
app[release.6634]: Running migrations:

…but partway through, these messages started appearing:

heroku[release.6634]: Process running mem=527M(101.5%)
heroku[release.6634]: Error R14 (Memory quota exceeded)

…ramping up until the 200% mark:

heroku[release.9599]: Process running mem=977M(190.3%)
heroku[release.9599]: Error R14 (Memory quota exceeded)

…and finally the termination of the release process:

heroku[release.9599]: Process running mem=1033M(201.7%)
heroku[release.9599]: Error R15 (Memory quota vastly exceeded)
heroku[release.9599]: Stopping process with SIGKILL

These messages came from Heroku’s process management layer, which terminated the memory-hungry release process with SIGKILL after the hard threshold of 1GB memory usage was breached. Repeat attempts hit the same issue.

I was confused: migrations should not consume much memory. While they create a lot of temporary objects (Django model classes and fields) in order to calculate the SQL to send to the database, such objects are all short-lived and should be garbage-collected fairly swiftly. Additionally, migrations worked fine on the local and CI environments, and they’d never had memory issues on previous Python versions.

It looked like there was a memory leak, and it was time to dig in.

Initial investigation

I first profiled memory usage of migrate locally using Memray, the memory profiler that I covered in my previous post, using:

$ memray run manage.py migrate

The profiles revealed that memory usage had slightly increased on Python 3.14 compared to 3.13, but did not find a memory leak (a pattern of continual growth). Still, I made some optimizations to defer some imports, saving about 30% of startup memory usage, and tried again, to no avail.

I then had the idea to profile on a Heroku dyno directly. After hacking the release process to not run migrations, I built a review app and SSH’d into its web server:

$ heroku ps:exec -a example-python-314-rspwtc --dyno web.1 bash
Establishing credentials... done
Connecting to web.1 on ⬢ example-python-314-rspwtc...
~ $

Initially, I tried using Memray’s live mode to profile the migrations as they ran:

$ memray run --live manage.py migrate

While this tool looks great for some situations, it didn’t really work here, especially since it seized up after Heroku terminated the server.

I then tried running the default memray run command:

$ memray run manage.py migrate
Writing profile results into memray-manage.py.724.bin

…then, on my local computer, I repeatedly ran this command to copy down the results file:

$ trash memray-manage.py.724.bin && heroku ps:copy -a example-python-314-rspwtc --dyno web.1 memray-manage.py.724.bin

I was a bit worried here that the Memray binary file might be corrupted due to copying it while memray run was generating it. But with a final truncated copy left over after the server crashed, I asked Memray to generate a flamegraph for it:

$ memray flamegraph memray-manage.py.724.bin

…and it worked! Kudos to the Memray team for making their output format usable even when incomplete.

This more detailed flamegraph revealed more than 50% of the memory usage was allocated in ModelState.render(), which creates temporary model classes:

class ModelState:
    ...

    def render(self, apps):
        """Create a Model object from our current state into the given apps."""
        ...
        return type(self.name, bases, body)

This information hinted that these temporary model classes were hanging around beyond their expected short lifetime, leading to the memory leak. For example, every model class could also end up in a list intended for debugging, but accidentally extending the lifetime of these temporary classes.

I decided to dig a bit deeper using machete-mode debugging, with the below snippet that captures the temporary model classes and logs details about them. I wrote this within the Django settings file, where it was guaranteed to run at Django startup time, before the migrate management command.

import atexit
import gc
import tracemalloc
import weakref
from itertools import islice

from django.db.migrations.state import ModelState

tracemalloc.start(2)

orig_render = ModelState.render

rendered_classes = weakref.WeakSet()


def wrapped_render(*args, **kwargs):
    cls = orig_render(*args, **kwargs)
    rendered_classes.add(cls)
    return cls


ModelState.render = wrapped_render


@atexit.register
def show_referrers():
    print(f"🎯 {len(rendered_classes)} classes referred to.\n")

    for cls in islice(rendered_classes, 2):
        print(f"🎁🎁🎁 {cls!r} 🎁🎁🎁")
        for i, referrer in enumerate(gc.get_referrers(cls), start=1):
            print(f"🍌 Referrer #{i}: {referrer!r}")
            if tb := tracemalloc.get_object_traceback(referrer):
                print("\n".join(tb.format(most_recent_first=True)))
            print()
        print()
        print()

Note:

  1. tracemalloc.start() starts Python’s built-in memory allocation tracking.
  2. The ModelState.render() method was monkeypatched with a wrapper that stores every temporary model class in a WeakSet.
  3. The @atexit.register-decorated function runs at the end of the program, and logs two things.
  4. The first piece of logging is the number of temporary model classes still alive at the end of the program, which should be close to zero. (Some may stick around from the final migration state.)
  5. The second piece of logging iterates over the first two live temporary model classes and logs their name and their referring objects, discovered via gc.get_referrers(). For each referring object, it also logs the traceback of where that object was allocated, using tracemalloc.get_object_traceback() (which is why tracemalloc.start() was needed at the beginning).
  6. The emojis are a bit of fun to make the log messages easier to skim through. I have no idea why I picked 🎁 and 🍌!!

The output from this hook was voluminous, even with the limit to the first two live classes. For example, here’s the output for a temporary ContentType model class:

🎁🎁🎁 <class '__fake__.ContentType'> 🎁🎁🎁
🍌 Referrer #1: <generator object WeakSet.__iter__ at 0x1234ef300>
  File "/.../example/core/apps.py", line 45
    for cls in islice(rendered_classes, 2):

...

🍌 Referrer #11: {'name': 'model', ..., 'model': <class '__fake__.ContentType'>}
  File "/.../.venv/lib/python3.14/site-packages/django/utils/functional.py", line 47
    res = instance.__dict__[self.name] = self.func(instance)
  File "/.../.venv/lib/python3.14/site-packages/django/db/models/fields/__init__.py", line 1210
    self.validators.append(validators.MaxLengthValidator(self.max_length))

I checked the live referrers for a few classes, and they all seemed to be expected. However, it did reveal just how many cycles exist between ORM objects. For example, model classes refer to their field objects, which in turn refer back to their model classes, thanks to Django’s Field.contribute_to_class() creating this reference:

def contribute_to_class(self, cls, name, private_only=False):
    ...
    self.model = cls
    ...

Anyway, from comparing the output between Python 3.13 and 3.14, I could see that no new references were being created on Python 3.14. It seemed likely that the incremental garbage collection algorithm was the culprit.

The workaround

Given the investigation, I wanted to work around the issue by forcing a full garbage collection sweep with gc.collect() after each migration file ran. I came up with the below code, saved as management/commands/migrate.py in one of the project’s Django apps. It extends the default migrate command to run gc.collect() after each successful migration (where “apply” is forwards and “unapply” is backwards).

import gc

from django.core.management.commands.migrate import Command as BaseCommand


class Command(BaseCommand):
    """Extended 'migrate' command."""

    def migration_progress_callback(self, action, migration=None, fake=False):
        """
        Extend Django’s migration progress reporting to force garbage
        collection after each migration. This is a workaround to keep memory
        usage low, especially because we have a low limit on Heroku. It seems
        the incremental garbage collector introduced in Python 3.14 cannot
        keep up with the migration process’s tendency to create many cyclical
        objects, so our best fallback is to force collection of everything
        after each migration is applied or unapplied.

        https://adamj.eu/tech/2026/04/20/django-python-3.14-incremental-gc/
        """
        super().migration_progress_callback(action, migration=migration, fake=fake)
        if action in ("apply_success", "unapply_success"):
            gc.collect()

It felt a bit hacky, but it did the trick! The review app succeeded to launch, showing a flat memory profile as before.

We then continued to deploy to staging and production without any issues, and the team have been happily using Python 3.14 for over a month now.

Fin

Well, that’s where the tale ends right now. After the incremental garbage collection algorithm is reverted in Python 3.14.5, I guess I’ll be able to remove this workaround.

While it would be nice to have incremental garbage collection work well, it’s clear that the current implementation has some issues. I think the core team is making the right call reverting it, but hopefully there will be energy to improve the feature for the future.

May your garbage be collected efficiently and without fuss,

—Adam

Read the whole story
jgbishop
82 days ago
reply
What a niche bug! Good to know that this exists, however...
Raleigh, NC
Share this story
Delete

Updating Gun Rocket through 10 years of Unity Engine

1 Comment

About 10 years ago I made Gun Rocket.

It was early in my game development journey. I had released 5 prototype games on Game Jolt, and it was time to sit down and make something worth paying for. I started with the idea "What if n++...but with the Asteroids ship?"

Development took about a month. The result was a game with 100 levels, multiple ships with different stats to pilot, and even a LAN multiplayer combat mode. Gun Rocket also stands out as my most lucrative personal project. After a successful Steam Greenlight process I was approached and licensed the Steam distribution rights for the game for a few years.

Recently I was reflecting on my game development journey. I tried to boot up Gun Rocket to play it. But it refused. No matter how hard I clicked the game would not open. The log is empty. I guess some driver or Windows API just doesn't work anymore.

So it is time to roll up my sleeves and bring Gun Rocket into 2026. Come along won't you? I could use the company.

Let's start by opening the game in Unity Editor. We'll test the game in its current editor version and re-acquaint ourselves here before moving on. The version of a Unity project is stored in /ProjectSettings/ProjectVersion.txt. It's a simple file with a simple purpose. Here's what I see:

m_EditorVersion: 5.5.0f3

Looking back at the git history of this file, I can see that I actually developed the game in 4.6.0p1 in 2015. The ProjectVersion file was created when migrating from 4.6 to 5.5 in 2018 hoping it would fix a bug (it didn’t). So there's our first interesting factoid about how Unity has changed. Crazy how time flies.

Anyway! Looks like Gun Rocket was most recently developed in Unity 5.5.0f3. The current Unity tech stream is 6.5 beta. That doesn't seem so bad! Just one major version bump, right?

WRONG!

Some time around 2017, Unity decided that its numbering was not corporate-friendly. At that time they were trying to expand from gaming into more verticals. I guess corporations love versioning their software by year, so that's what Unity did. It makes the messaging about long-term support easier. Let's say Unity supports a release for 3 years. When does that end? It's much easier to talk about that for Unity 2017 (2017 + 3 = 2020) than for Unity 5.5 (???).

Nowadays Unity is back to simple numbers. Today’s major version number is 6. At least...that's what the website says. Unity version numbers now look something like 6000.4.1f1. I find this hilarious. It reminds me of Loony Tunes technology naming. Roadrunner Catcher 3000 anyone? Again, there is a good reason for this. 6000 > 2023. 2023 is Unity's last year-named version. So all of the version sorting code will continue to Just Work TM. A Good Reason. But I still find it funny.

So I open Unity Hub and look for 5.5.0f3. It's not one of the readily available options. Unity presents Official Releases (long-term support and the latest supported minor release 6000.4.1f1), Pre-releases (currently just the 6000.5.0b1 beta), and ArChIvE. We'll be spending a lot of time in the archive. I like to think of it as the back room in the basement where folks store things they just can't bear to part with yet. It's super excellent that all of these versions are kept around. It means my ambition to bring Gun Rocket into 2026 has legs - if only barely. The archive only goes back to Unity 5. Good thing I upgraded from 4.6 in 2018!

Wow, all this history and we haven't even opened the editor yet. Let's try that now.

It does the same thing as the game build on Steam: just closes with no information in the log. Shoot.

Some Google research tells me this might be related to the license check. Unity 5 pre-dates Unity Hub. So sure, it makes sense that it could be a license check issue. I try to open from the Unity.exe rather than through Hub as suggested. No luck.

Ok then, let's try a newer version. I wanted to verify the game in 5.5, but I guess I am out-of-luck. I nab the most recent Unity 5: version 5.6.7f1. Again, it doesn't launch from Unity Hub, but that's what I expect at this point. What about launching from the Unity.exe?

Adblock test (Why?)

Read the whole story
jgbishop
83 days ago
reply
Good read
Raleigh, NC
Share this story
Delete
Next Page of Stories