Performance Optimization of bsdiff for In‑Car Navigation OTA Updates

With the increasing connectivity of in‑vehicle devices, car navigation systems have shifted from offline packages to online iterative updates. However, the Android hardware in many car head units is far less powerful than smartphones, leading to issues such as inability to download new version packages and long update times that cause stuttering.

To improve user experience, Amap (Gaode) technology team launched a project to address these problems. This article summarizes the performance‑optimization practice of using binary‑diff (bsdiff) for self‑updating in‑car navigation.

Comparison of diff update schemes

Besides distributing full installation packages, incremental packages (diff) can be delivered, and the client applies a patch to the old version. Popular diff tools include bsdiff, Xdelta3 and Courgette. Courgette focuses on executable files, while navigation updates also contain images and other resources, so the comparison focuses on bsdiff and Xdelta3.

Experimental results (see image) show that bsdiff produces much smaller diff files but its patching process is time‑consuming, whereas Xdelta3 patches quickly but consumes large memory. Because the navigation system has less than 100 MB of free RAM, Xdelta3’s memory usage is unacceptable, so bsdiff was chosen.

Limitations of the vanilla bsdiff and improvements

Memory consumption of 10–35 MB during patching.

Patch time around 3 minutes.

By adopting the Chromium‑based bsdiff variant that replaces the default suffix‑sort algorithm with divsufsort, memory usage dropped to 10–20 MB and patch time to about 25 seconds, but it was still too long for the target.

Optimization practice

The goal was to keep total update time under 6 seconds and memory usage under 2 MB. The following measures were taken:

Memory‑saving scheme

A sliding‑window buffer was added to the bsdiff patch format, enabling streaming processing of files so that only a small window is kept in memory.

Algorithmic scheme

The main bottleneck after memory optimization was the Bzip2 decompression step. Replacing Bzip2 with a simpler run‑length encoding (RLE) algorithm reduced CPU load. Although the resulting patch files were larger, a second compression (tar.bz2 or zip) restored comparable overall compression ratios while only slightly increasing disk usage on the client.

Performance comparison

After the full set of optimizations, memory consumption became O(1) (≈2 MB) and patch time reduced to 3–5 seconds on ARM car head units, as shown in the figures.

Conclusion

Optimizing bsdiff enabled Amap’s in‑car navigation to achieve significantly faster OTA updates with minimal resource impact, paving the way for future feature delivery.