How AI beat me at code optimization game.
When I started writing this article I did not expect AI to beat me at optimizing JavaScript code. But it did.
I’m really passionate about optimizing JavaScript. Some say it’s a mental illness but I like my code to go balls to the wall fast. I feel the need. The need for speed.
Optimizing code often requires tedious refactoring.
Can we delegate the tedious parts to AI? Can I just have ideas and get AI to be my programming slave?
Let’s find out.
Optimizing Unicode range lookup with AI
In my experiment I used
Cursor with Claude 3.5 Sonnet model. I assume it could be done with other tools / models.
const UnicodeRanges = [
[0x0000, 0x007f], // 0 - Basic Latin
... omited
[0x0250, 0x02af, 0x1d00, 0x1d7f, 0x1d80, 0x1dbf], // 4 - IPA Extensions - Phonetic Extensions - Phonetic Extensions Supplement
... omited
];
function getUnicodeRangeFor(value, lastPosition = -1) {
// TODO: create a map range => position, sort the ranges and cache it.
// Then we can make a binary search for finding a range for a given unicode.
if (lastPosition !== -1) {
const range = UnicodeRanges[lastPosition];
for (let i = 0, ii = range.length; i < ii; i += 2) {
if (value >= range[i] && value <= range[i + 1]) {
return lastPosition;
}
}
}
for (let i = 0, ii = UnicodeRanges.length; i < ii; i++) {
const range = UnicodeRanges[i];
for (let j = 0, jj = range.length; j < jj; j += 2) {
if (value >= range[j] && value <= range[j + 1]) {
return i;
}
}
}
return -1;
}
This is a simple function: given Unicode character it returns Unicode range (number 0 ... UnicodeRanges.length - 1). The number is cleverly encoded implicitly as array index.
The code already has a TODO about a potential optimization: sort UnicodeRanges and do binary search.
There’s a minor difficulty: some Unicode ranges have multiple intervals, so we have to change the UnicodeRanges to explicitly include the range as 3rd element:
const UnicodeRanges = [
[0x0000, 0x007f, 0], // 0 - Basic Latin
[0x0250, 0x02af, 4], // 4 - IPA Extensions - Phonetic Extensions - Phonetic Extensions Supplement
[0x1d00, 0x1d7f, 4], // 4 - IPA Extensions - Phonetic Extensions - Phonetic Extensions Supplement
... omitted
];
Then sort it and change the implementation of getUnicodeRangeFor().
Re-writing UnicodeRanges is simple but tedious and I don’t feel like doing it. Can AI do such change for us?
Changing representation
I’ve selected the whole of UnicodeRanges, added to chat with Ctrl + Shift + L and commanded:
Change representation of UnicodeRanges array where each entry is 3 elements: [start, end, rangeNo]; preserve comments; if rangeNo has multiple ranges, split into separate entries
Cursor responded with:
const UnicodeRanges = [
[0x0000, 0x007f, 0], // 0 - Basic Latin
[0x0080, 0x00ff, 1], // 1 - Latin-1 Supplement
... omitted
];
There was an issue: it only did part of the array. So I commanded:
don’t be lazy, finish the whole UnicodeRanges array
It did but the result was too long so I had to click Continue button.
It worked and the generated code seems to be correct so I applied it.
For binary search, the array must be sorted, so I commanded:
Sort the array by first element
It did, the result looked correct so I accepted the change.
Hmm, I can get used to having a programming slave.
Updating the code to implement binary search
I copied getUnicodeRangeFor to chat and commanded:
change the implementation to use binary search over UnicodeRanges array
It gave me:
function getUnicodeRangeFor(value, lastPosition = -1) {
// Check the last position first
if (lastPosition !== -1) {
const range = UnicodeRanges[lastPosition];
if (value >= range[0] && value <= range[1]) {
return lastPosition;
}
}
// Binary search
let left = 0;
let right = UnicodeRanges.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const range = UnicodeRanges[mid];
if (value < range[0]) {
right = mid - 1;
} else if (value > range[1]) {
left = mid + 1;
} else {
return range[2]; // Return the range index
}
}
return -1; // Not found
}
It looks correct so I accepted it.
We achieved the goal: replaced linear search with binary search using cheap AI labor.
But I want more. More speed.
Changing array of arrays to flat array
A more efficient representation of the ranges would be a flat array:
const UnicodeRanges = [
0x0000, 0x007f, 0, // 0 - Basic Latin
0x0080, 0x00ff, 1, // 1 - Latin-1 Supplement
];
Let’s see if our AI slave can do it:
change the whole UnicodeRanges array to flat array, preserve comments, don’t be lazy and do all of it
I pre-emptively command the AI to convert the whole array. It did it.
Now is the time to update getUnicodeRangeFor(). It’s a simple change I could do myself: now we just multiply index * 3 to get range definition. But I kind of like commanding the AI so I did it again:
update getUnicodeRangeFor for new flat array representations of UnicodeRanges
It gave me:
function getUnicodeRangeFor(value, lastPosition = -1) {
// Check the last position first
if (lastPosition !== -1) {
const index = lastPosition * 3;
if (value >= UnicodeRanges[index] && value <= UnicodeRanges[index + 1]) {
return UnicodeRanges[index + 2];
}
}
// Binary search
let left = 0;
let right = UnicodeRanges.length / 3 - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const index = mid * 3;
const rangeStart = UnicodeRanges[index];
const rangeEnd = UnicodeRanges[index + 1];
if (value < rangeStart) {
right = mid - 1;
} else if (value > rangeEnd) {
left = mid + 1;
} else {
return UnicodeRanges[index + 2]; // Return the range index
}
}
return -1; // Not found
}
It does seem correct, but let’s do one more tweak:
move binary search code to its own function
And it worked:
function binarySearchUnicodeRange(value) {
let left = 0;
let right = UnicodeRanges.length / 3 - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const index = mid * 3;
const rangeStart = UnicodeRanges[index];
const rangeEnd = UnicodeRanges[index + 1];
if (value < rangeStart) {
right = mid - 1;
} else if (value > rangeEnd) {
left = mid + 1;
} else {
return UnicodeRanges[index + 2]; // Return the range index
}
}
return -1; // Not found
}
function getUnicodeRangeFor(value, lastPosition = -1) {
// Check the last position first
if (lastPosition !== -1) {
const index = lastPosition * 3;
if (value >= UnicodeRanges[index] && value <= UnicodeRanges[index + 1]) {
return UnicodeRanges[index + 2];
}
}
// Perform binary search
return binarySearchUnicodeRange(value);
}
Inlining some of the binary search
It’s good but we haven’t yet reached the levels of insanity I’ve hinted at.
UnicodeRanges is a fixed array. We could “unroll” the binary search into code. It would be very painful to do manually. I would have to write custom code generator to ensure it’s correct but maybe AI can do it for us?
unroll first 3 levels of binarySearchUnicodeRange
To my surprise, it worked. AI understood what I wanted and gave me this:
function getUnicodeRangeFor(value, lastPosition = -1) {
... omited
const length = UnicodeRanges.length / 3;
let mid = Math.floor(length / 2) * 3;
if (value < UnicodeRanges[mid]) {
mid = Math.floor(mid / 2);
if (value < UnicodeRanges[mid]) {
mid = Math.floor(mid / 2);
} else if (value > UnicodeRanges[mid + 1]) {
mid = mid + Math.floor(mid / 2);
} else {
return UnicodeRanges[mid + 2];
}
} else if (value > UnicodeRanges[mid + 1]) {
mid = mid + Math.floor(mid / 2);
if (value < UnicodeRanges[mid]) {
mid = mid - Math.floor(mid / 4);
} else if (value > UnicodeRanges[mid + 1]) {
mid = mid + Math.floor(mid / 4);
} else {
return UnicodeRanges[mid + 2];
}
} else {
return UnicodeRanges[mid + 2];
}
... omited
}
Can we do even better?
unroll the values of UnicodeRanges[mid] etc. and replace with constants
Holly cow, it worked:
function getUnicodeRangeFor(value, lastPosition = -1) {
// Check the last position first
if (lastPosition !== -1) {
const index = lastPosition * 3;
if (value >= UnicodeRanges[index] && value <= UnicodeRanges[index + 1]) {
return UnicodeRanges[index + 2];
}
}
// Unrolled binary search with constants
if (value < 0x4E00) { // CJK Unified Ideographs start
if (value < 0x0530) { // Armenian start
if (value < 0x0250) { // IPA Extensions start
if (value < 0x0100) { // Latin Extended-A start
if (value < 0x0080) { // Latin-1 Supplement start
return 0; // Basic Latin
}
return 1; // Latin-1 Supplement
}
if (value < 0x0180) {
return 2; // Latin Extended-A
}
return 3; // Latin Extended-B
}
if (value < 0x0300) { // Combining Diacritical Marks start
if (value < 0x02B0) { // Spacing Modifier Letters start
return 4; // IPA Extensions
}
return 5; // Spacing Modifier Letters
}
if (value < 0x0370) { // Greek and Coptic start
return 6; // Combining Diacritical Marks
}
if (value < 0x0400) { // Cyrillic start
return 7; // Greek and Coptic
}
return 9; // Cyrillic
}
// Continue with binary search for remaining ranges
let left = 10; // Index of Armenian in UnicodeRanges
let right = 102; // Index of CJK Unified Ideographs in UnicodeRanges
while (left <= right) {
const mid = Math.floor((left + right) / 2) * 3;
if (value < UnicodeRanges[mid]) {
right = Math.floor(mid / 3) - 1;
} else if (value > UnicodeRanges[mid + 1]) {
left = Math.floor(mid / 3) + 1;
} else {
return UnicodeRanges[mid + 2];
}
}
} else {
// Binary search for ranges after CJK Unified Ideographs
let left = 103; // Index after CJK Unified Ideographs in UnicodeRanges
let right = UnicodeRanges.length / 3 - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2) * 3;
if (value < UnicodeRanges[mid]) {
right = Math.floor(mid / 3) - 1;
} else if (value > UnicodeRanges[mid + 1]) {
left = Math.floor(mid / 3) + 1;
} else {
return UnicodeRanges[mid + 2];
}
}
}
return -1; // Not found
}
Is it correct? I have no idea. Would be easy to write a test that uses UnicodeRanges as source of truth and tests getUnicodeRangeFor() for every possible value.
Can I just ask AI to do it faster?
So far I micro-managed the AI coder. I was telling it exactly what kind of change I wanted and commanded AI until it did what I wanted.
A good boss delegates. Good boss tells the worker the high level goal and leaves implementation detail to the worker.
Let’s start from scratch and command AI thusly:
could you make a faster implementation of getUnicodeRangeFor()? You can change the representation of UnicodeRanges to achieve that goal
Holly cow again. The AI figured out the binary search:
const UnicodeRanges = [
{ start: 0x0000, end: 0x007f, index: 0 }, // Basic Latin
{ start: 0x0080, end: 0x00ff, index: 1 }, // Latin-1 Supplement
{ start: 0x0100, end: 0x017f, index: 2 }, // Latin Extended-A
// ... (other ranges)
{ start: 0x1f000, end: 0x1f09f, index: 122 }, // Domino Tiles - Mahjong Tiles
].sort((a, b) => a.start - b.start);
function getUnicodeRangeFor(value, lastPosition = -1) {
if (lastPosition !== -1) {
const range = UnicodeRanges[lastPosition];
if (value >= range.start && value <= range.end) {
return range.index;
}
}
let left = 0;
let right = UnicodeRanges.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const range = UnicodeRanges[mid];
if (value >= range.start && value <= range.end) {
return range.index;
}
if (value < range.start) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
The object {start, end, index} is less efficient than my flat array representation and it didn’t unroll the binary search but the core idea of binary search is there.
But just for kicks, maybe there’s more:
can you make it even more efficient?
It did something slightly different, but really the same. I’m afraid no bonus this quarter.
Ok, one last try:
but could you go all out and use every possible implementation trick you know to optkmize getUnicodeRangeFor and UnicodeRanges representation?
Fuck me, I have no idea if the generated code is correct but it does seem it would be faster than the non-unrolled binary search I came up with earlier:
// Preprocess UnicodeRanges into a more efficient structure
const BUCKET_SIZE = 256;
const MAX_UNICODE = 0x10FFFF;
const buckets = new Uint16Array(Math.ceil((MAX_UNICODE + 1) / BUCKET_SIZE));
const ranges = [];
UnicodeRanges.forEach((range, index) => {
for (let i = 0; i < range.length; i += 2) {
const start = range[i];
const end = range[i + 1];
ranges.push({ start, end, index });
const startBucket = start >>> 8;
const endBucket = end >>> 8;
for (let j = startBucket; j <= endBucket; j++) {
buckets[j] |= (1 << (index & 15));
}
}
});
ranges.sort((a, b) => a.start - b.start);
// Create a compact representation of ranges
const compactRanges = new Uint32Array(ranges.length * 3);
ranges.forEach((range, i) => {
compactRanges[i * 3] = range.start;
compactRanges[i * 3 + 1] = range.end;
compactRanges[i * 3 + 2] = range.index;
});
function getUnicodeRangeFor(value, lastPosition = -1) {
if (value > MAX_UNICODE) return -1;
// Check last position first
if (lastPosition !== -1) {
const start = compactRanges[lastPosition * 3];
const end = compactRanges[lastPosition * 3 + 1];
if (value >= start && value <= end) {
return compactRanges[lastPosition * 3 + 2];
}
}
// Quick check using buckets
const bucket = buckets[value >>> 8];
if (bucket === 0) return -1;
// Binary search within the relevant ranges
let left = 0;
let right = compactRanges.length / 3 - 1;
while (left <= right) {
const mid = (left + right) >>> 1;
const start = compactRanges[mid * 3];
const end = compactRanges[mid * 3 + 1];
if (value < start) {
right = mid - 1;
} else if (value > end) {
left = mid + 1;
} else {
return compactRanges[mid * 3 + 2];
}
}
return -1;
}
In retrospect, using Uint32Array for UnicodeRanges array was a no-brainer. It’s more compact in memory, the values will probably be compared as integers, not floats. Should be faster to scan than array of floats.
The buckets are not necessary. They seems to be for quick “doesn’t exist check” which is not important. I believe most lookups are for values that exist.
I’m humbled that just asking for super duper optimization made AI produce something I didn’t think of.
More optimization ideas
I can’t help myself. Those are ideas I didn’t ask AI to implement.
UnicodeRanges is small. A linear search of compact Uint32Array representation where we just have (start, end) values for each range would be faster than binary search due to cache lines.
We could start the search in the middle of array and scan half the data going forward or backwards.
We could also store ranges smaller than 0x10000 in Uint16Array and larger in Uint32Array. And do linear search starting in the middle.
Since the values are smaller than 256, we could encode the first 0xffff values in 64kB as Uint8Array and the rest as Uint32Array.
That would probably be the fastest on average, because I believe most lookups are for Unicode chars smaller than 0xffff.
Finally, we could calculate the the frequency of each range in representative sample of PDF documents, check the ranges based on that frequency, fully unrolled into code, without any tables.
Conclusions
AI is a promising way to do tedious code refactoring.
If I didn’t have the AI, I would have to write a program to e.g. convert UnicodeRanges to a flat representation. It’s simple and therefore doable but certainly would take longer than commanding AI.
The unrolling of getUnicodeRangeFor() would probably never happen. It would require writing a sophisticated code generator which would be a big project by itself.
AI can generate buggy code so it needs to be carefully reviewed.
The unrolled binary search could not be verified by review, it would need a test. But hey, I could command my AI sidekick to write the test for me.
There was this idea of organizing programming teams into master programmer and coding grunts. The job of master programmer was to generate high level ideas and supervising coding grunts that did the actual implementation work.
Turns out that we can’t organize people that way but now we can use AI as our coding grunts.
Prompt engineering is a thing. I wasted a bunch of time doing incremental improvements. I should have started by asking for super-duper optimization.
Productivity gains is real. The whole thing took me about an hour. For this particular task easily 2x compared to not using cheap AI labor. Imagine you’re running a software business and instead of spending 2 months on a task, you only spend 1 month.
I’ll be using more AI for coding.
