On the design of Compact Elastic Binary Trees (cebtree)

Those who often hear me discuss about my week-end projects have been accustomed to hearing about deuterium fusion (that's for another post), laser engraving, and the compact version of the ebtrees, aka compact elastic binary trees, without knowing all the details. That's what we'll be discussing here.

A long history

Self-organizing trees

It started very early during the development of ebtrees, in which the same node appears twice, once as a node and once as a leaf. In 2007, when I managed to build self-organizing trees to handle duplicates, and noticed that all that was needed to insert, delete, and visit nodes, was to remember the node from which to restart or where to attach, and that it was never needed to go upwards in the tree for such operations, that made me think that maybe this type of structure would also work to arrange data without uplink and without keeping any relation between the node's depth and the key it conveys. Adding a new duplicate value would only require to measure the depth of the penultimate branch and allow to grow the next one until it becomes as long. If it was already as long, then another one just had to be added above it. For example below, we're adding 4 successive entries to a duplicate sub-tree that already contains 4 identical keys ordered by their insertion sequence. The number in the leaf indicates the arrival order for each of them:

XORing branches

18 months later, when optimizing the lookup algorithm by comparing the XOR between the looked up key and the node's key with the node's position, I figured that the XOR between the two branches was always necessarily lower given that these branches have more bits in common, and that maybe we could afford not to store the depth if the XOR between the key and node, and the XOR between the two next branches already allowed us to figure where we're located in the tree. An intuition was that, just like in the ebtrees, we can detect that the searched key is not there when the XOR of the two branches is no longer smaller than between the key and current node, or that we're reaching a leaf if the XOR is higher than the previous one.

In the example below, we successively insert the keys 6, 4, then 5. 6 being the first entry, it's the node-less entry (it only has a leaf). Then 4 is inserted, it has 4 and 5 below it, then 5 is inserted below 4, so it has 4 and 5 as its leaves:

In red is indicated the XOR between the branches. The node-less leaf is a special case that loops to itself, so its descendants are the same. 4 splits between 5 and 5, so the XOR of the branches here is 5^6=3. 5 splits 4 and 5 so its XOR is 4^5=1.

When descending along the branch to key 4, a XOR of 3 is first met at node 4, then a XOR of 1 is met at node 5, then when going down to node 4 (which is the same as the one on top), we're seeing a XOR of 3 again. 3 being higher than previous value 1 proves that we have looped, so 4 here is no longer a node but a leaf.

Similarly, when looking up a value, XORing the searched value with the node's value indicates if we have a chance to find it below or not. As soon as the XOR between a node's branches is higher than the XOR between the looked up value and the node's value, we're certain it cannot be there anymore.

All of this was fun and interesting, but turning intuitions into new week-end projects is never trivial nor necessarily desired when there are already plenty of other activities, so aside a few ideas from time to time when improving ebtrees, not much progress was done in this area for a while.

First limited implementation

Several years later, in 2014, while thinking about a super-compact memory allocator that I'd call "water drop alloc" ("wdalloc") to illustrate how releasing a drop of water in the middle of two other ones that touches them instantly becomes a larger one, I was thinking that a more compact variant of ebtrees would be particularly suited for that purpose if they would index the pointer itself as the key instead of a stored key. An example of the principle is seen below where freeing a block of length 4 at address 5 results in a new free block of 11 by fusing it with the two adjacent blocks, thanks to trivial adjacent address lookups:

Thus I implemented the "space efficient trees" by then for that purpose, proving that the concept of descending with only two pointers and nothing else is sufficient to build a complete tree:

That's it, only two pointers and nothing else, i.e. 16 bytes on 64-bit architectures. Compared to ebtrees which take 40 bytes (or even 48 with alignment) on such architectures, it's a nice saving!

Here the leaf keys would just be the nodes' addresses, so there was no additional storage, and two pointers were really the only required storage for each allocatable area, with nothing having to be stored for as long as the node is in use.

That application was well suited to the limited experience I had accumulated by then about these new trees:

• no need to look up the pointer upon free(), the node is at a fixed place relative to the pointer passed to free(). An optional lookup would allow to detect double-free, though.
  
• lookup_ge() and lookup_le() were sufficient to find adjacent entries, as well as to index free objects by their size.
• there was no duplicate by definition since the key is the object's address
• all operations require to know the root, which in this case was the origin of the allocation arena.
• space saving: only two pointers per entry, thus limiting granularity to dual-word, which preserves the dual-word alignment guarantees generally assumed by C ABIs.
  

The first tests showed that the performance was significantly lower than with other allocators, and the idea of scaling that to threads and having to lock the tree achieved to put the final nail in the project's coffin.

Next attempts

However this confirmed that the basic algorithm worked. I then started to try to better organize the ebtree code to support the relative adressing variants that had been lying in their own branch for 3 years, to support multiple addressing modes, and try to merge both the standard and the compact models. That was tough work that spanned from 2014 to about 2017, while gaining in complexity over time and slowing progressively down. Worse, every time I had an idea about that topic, it required a full week-end to re-enter that code in the process of being reorganized, and the week-end was often over before I had the time to evaluate my idea.

In early 2020, we were locked down with week-ends becoming particularly boring, and I had to keep my mind busy, so it was a sane week-end activity to get back to that project and try to complete it. I tried to force myself to proceed in baby steps, in order to avoid the trap of getting stuck into the code being reorganized:

• first, I actually had to re-learn how that whole thing worked, verify the properties that I can use, and demonstrate them. That kept me busy with pen and paper for a several week-ends in the garden during a fortunately sunny spring.
• second, I had to verify if storing ordered duplicates was possible at all, given that my wdalloc experiment never made use of them. It took me a while to convince myself that the self-organizing tree was not suitable here since we were not storing the depth to distinguish between them:
  
  
  
  

  
  It's visible above that the XOR between all branches is 0 in the duplicates, so there's no way to get out of them and find a leaf. In ebtrees actually what breaks the loop is the fact that we rely on the depth counter associated with each node: when finding a node whose depth is higher than the previous one, it indicates we have looped, thus that the last node was in fact a leaf.
  

• For a long time I also considered storing a couple made of the node's pointer and the key to differentiate them, but I didn't like it because keys would be retrieved in their in-memory order, not in the insertion order, and that was not great for certain operations where it's mandatory to know which one will be used. In addition, that could have costed a lot to delete an element, requiring to visit many duplicates before finding the right one.
  
  
  
   
• Finally I managed to design a list-based mechanism that worked on paper using tagged pointers. I had the intuition that it might possibly also work without tagged pointers, but at least I knew I was having a solution which allowed to delete any duplicate in O(1) after locating it in O(logN). There were many special cases and that was significantly complicating the design.

I left that quest for a while. I had proven my design, and the lockdown period was not something that could be associated with desires of creativity :-/ Adding to that the fact that diving into this on week-ends is often non-productive as it takes a whole week-end to figure again how all of this works, it became discouraging after a few attempts.

I forced myself to work on it again 9 months later during the new year's vacation, continuing to integrate it into the reorganized branch of ebtree. And that was a big mistake: the state of that branch made it too hard to make any progress efficiently, to the point that I'm now wondering if there's anything to reuse in the branch collecting that long work.

Restart from scratch with first success

Finally I decided on a summer vacation of 2023 that the compact tree code needed to be forked into its own project, and restarted from scratch there, intentionally leaving the complexity of dealing with duplicates aside for a first implementation, ignoring some of the initially planned optimizations, trying to make it work without tagged pointers so as to keep them for later if needed (e.g. for duplicates), and all done with a single function to deal with all types and operations in order not to reproduce the maintenance difficulties met with ebtrees. Another element taken into consideration is the extension of the API to support a different key offset, permitting in some cases to avoid repeating a key in certain structures when it's already present but not immediately after the tree node:

After all this, v0.1 was finally released mid-september 2024 with support for all types but no duplicates, as planned for the first version. I could find a good use for this in haproxy 3.1: variables generally have a short name with a small value, and couldn't afford to use a huge ebtree indexing node, so they were still in a linked list.  We already knew that variables were gaining in popularity and that their cost would increase linearly with their number. Thus it was a perfect opportunity to migrate their indexing to cebtree at no extra cost. This change revealed that a config with 100 variables improved its performance by 37% with no size increase. Great!

Need for duplicates again

Studying opportunities for other areas of haproxy like maps, acls, timers etc revealed that it was not that trivial, because all of these need ordered duplicates. So that was a good opportunity to try to attack that problem again.

The previous work done during lockdown consisted in inserting lists between a node and a leaf. The idea was that in all cases we're dealing with pointers to nodes, and that duplicates can be arranged as a list without losing information nor needing extra storage, if we only use list elements as a spacer:

The principle is not very complex. When adding a duplicate key, we're inserting it as a list element between the previous leaf and the node that pointed to it. The inserted node has its left pointer pointing to the leaf and the right one pointing to itself. When adding new duplicates, the new duplicate is inserted exactly the same way, and the previous list element points to from its right pointer it. The list can thus be extended infinitely. What is nice is that when looking up the value, it is detected that there are multiple keys because regardless of the number of list elements, the left and the right pointers point to a node having the same value (possibly the same node itself). When such a duplicate entry is detected, it is always the last inserted one (e.g. the blue one on the diagram above), then the first leaf is always reachable via last->right->left. Then in order to visit the next duplicate, either the current node is this leaf, in which case the next one is last->right, or it isn't, then it is necessarily one of the duplicates, and the next node is the always node->right until the last one is reached (the one that was first found). This construct is super interesting because it provides the following properties:

• appending a new entry always places it at the end
• visiting entries always start from the first inserted ones
  
• it is always possible from a node to instantly find its neighbors in order to delete it, thus making it relatively easy to "pick" elements (i.e. find and detach the next one) in insertion order. 
• list entries behave like nodes in that they always point to adjacent values that fall within as large a prefix length as was previously encountered (since they are equal).
  

Finally v0.2 was issued with this support for duplicates mid february 2025. It's now considered feature-complete!

Working on performance

Performance comparisons show that, as expected, this cebtree is less performant than ebtree due to having to compare two nodes per level during the descent, only one of which is to be useful, thus effectively doubling the number of memory reads compared to ebtree.

In addition, large strings are severely affected because just like in non-radix trees such as  rbtrees, they have to be compared from the beginning at each level in order to detect a leaf, so the average lookup cost is L*log2(N) where L is the average string length and N the number of strings. Since we didn't make use of tagged pointers yet, it was time to try to introduce them to designate leaves, allowing to restart the comparison from the previous split point so that strings are now entirely read only once during the lookup.

The approach that seemed to work on paper during lockdown proved its value without affecting duplicate lists, in that it is super simple: only pointers to a leaf are tagged. This means that pointers to lists are not tagged, and that a tagged pointer inside a list of duplicates necessarily indicates the first leaf. Also, insertion/removal operations remain extremely simple as the pointer is preserved. The total number of changes in the code to support tagged pointers remained very low, most of them were related to the addition of wrappers to avoid directly dereferencing tagged pointers. For this, pointer types have been changed in the code so as to always know what points to a node and what is a tagged node pointer. This requires to change the code where a cebtree was created by a "struct ceb_node*", to change it to "struct ceb_root*", but that's all.

An update of the "6,4,5,5,5" tree above with tagged pointers for leaves now gives the following (tagged pointers are on red links):

Now it's only slightly slower than ebtree on large strings (still due to twice the keys being read during the descent), but sometimes even slightly faster on small strings, probably due to the lower memory bandwidth needed thanks to the much smaller nodes. This is currently found in the master branch of the project.

Current state

The current state looks functional. The code contains some functional and performance tests. The usage remains very close to ebtree except that the tree root has to be passed to all operations (in ebtree, delete/next/prev etc didn't require the root since it was possible to navigate upwards).

The choice between duplicates or unique keys is specified in the function name now, we don't tag the root to indicate how it will be used anymore; it was indeed found after using ebtrees like this for a while that it makes the code not particularly obvious to understand, as one needs to locate the initialization of the tree to know what to expect after an insert() call. Now at least the intent will be explicit in the code.

This also simplifies the root initialization as the root node now only needs to be set to a NULL pointer for an empty tree, then some insert() calls can be performed to insert elements. Example below (warning! no error checking):

struct ceb_root *root;

struct ceb_node *node;

struct entry {

    struct ceb_node node;

    char *string;

} *entry; 

 

/* index all arguments */ 

while(arg < argc) {

    entry = calloc(1, sizeof(*entry));

    entry->string = strdup(argv[arg]); 

    cebis_insert(&root, &entry->node);

    arg++;

}

 

/* list all arguments, sorted */

node = cebis_first(&root);

while (node) {

    printf("@%p = %s\n", node, container_of(node, struct entry, node)->string);

    node = cebis_next(&root, node);

}

Just use cebuis_* above to enforce unique keys.

Cost comparison with ebtree

All operations are in O(logN)  while ebtree has several operations in O(1) (next/prev/delete). In addition, for certain operations such as next/prev/delete, cebtree requires to record the restart pointer during a descent, reach the desired leaf and complete the operation from the recorded pointer. Just like with a next/prev, this extra cost is amortized to one extra level, but it can reach up to logN for 1/N nodes and could be averaged to logN/N.

In addition, the extra cost compared to ebtree comes from the fact that cebtree, just like other non-radix trees (rbtree etc), needs to visit two branches to figure which one to descend. ebtree avoids this by storing the depth value inside the node. These extra reads may consume more memory bandwidth for large keys, but given that the node itself is 2.5-3 times smaller, the extra cost for small keys can still be absorbed by the lower cost of retrieving the node from memory. However, this extra cost could have an impact on TLB misses when using indirect accesses (cebis_* etc).

Tests performed on haproxy on a laptop with the map/acl pattern reference showed:

• a tiny performance increase when loading a map made of 17 million IPv4 addresses and masks (22.0 seconds down to 21.5 seconds); these are short 17-character strings. The resulting memory saving was 400 MB.
  
• a moderate increase when loading a map made of 1 million user agents (much larger strings). The time went up from 2.475 seconds to 2.711 seconds. The memory saving was 24 MB.

Thus it can make sense to use this for stuff that's mostly related to configuration or that doesn't change often and is mostly looked up (i.e. config object names).

 

What's left to be done

First, the documentation in the code is still incomplete. Now that the API got clearer, the doc should be should be finished. In the worst case some types will get renamed, which is no big deal. The doc must be done before 0.3 is released anyway.

Some things are still in the state of reflection:

• shouldn't we use a different root type for duplicates vs unique trees ? It could avoid mistakes caused by copy-paste. We could very well do that in exposed function prototypes only so as not to carry these down the code.
  
•  some operations that exist in ebtree were not implemented. One of them is the longest match, typically used to look up IP addresses within ranges. It's still unknown at this point if this can be implemented with the current model (maybe it would require to slightly change the key representation, in ebtree the prefix length is passed and stored separately).
• some long but still incomplete studies indicate that the code could almost support properly ordered atomic operations. The only real limitation is deletion that is not compatible with parallel insertion or lookup. One first approach could be to use upgardable rwlocks like progressive locks and take a shared lock for all operations, and upgrade it to an exclusive lock only when committing the removal. This would result in a very short locking time, though all visitors would still need to write-access a shared memory area to grab the read lock, and a moderate deletion rate could suffice to purge visitors too often. Another solution might be to consider alternate approaches such as RCU.
• implementation of relative pointers was started but put to a pause for now. It's convenient to index files in-place (e.g. logs etc), but I didn't have immediate use for this and it further complicates the development. It will have to be done, though.

Future work 

Simplifying the trees to the extreme of requiring only two pointers, just like a list, opens some perspectives:

• maybe it would be useful to support to optionally implement the parent pointers in the node so as to decide between performance and space.
• the work initially done on ebtrees to try to factor the code went in the wrong direction by making it too difficult to use and maintain. On the opposite, the work done on cebtree preserved maintainability despite supporting multiple types (u32, u64, long, addr, blocks, strings, indirect blocks, indirect strings). It looks like ebtree would benefit from rolling back to before the change and adopting a cebtree-like approach.
• the duplicate lists of cebtree look way better than the duplicate trees of ebtree, and maybe we could significantly improve ebtree's performance in schedulers by adopting the same duplicates (duplicate values are frequent in scheduler due to the timer's resolution).
  
• maybe ebtree could be built as an extended cebtree in the end, then it could be nice to re-merge them into a single project.
• studying the interest of self-locking nodes following the same principle as mt_lists could also be interesting, though the visit cost might become high.
  

Links

The code in its current state is available here:

• cebtree : version 0.1 is the most basic (no duplicates). Version 0.2 supports duplicates without using tagged pointers. It can be seen as a reference about what can be done when tagged pointers are not desired. The current version supports everything including tagged pointers and is still in development.
• ebtree : version 6 is the production one. Version 7 is the one that tries to factor all the code and that is not considered production ready.
• plock: the upgradable R/W progressive locks will probably be the next step to support parallel insertions and lookups with exclusivity only on the delete operation.
• mt_list: the self-locked lists have concepts that might be reusable here, probably even lighter since nodes are accessible in a single direction at a time. This deserves to be studied.
  

Adding a cheap and simple RTC to Rockchip devices

Background

There are plenty of nice devices these days designed around ARMv8.2 SoCs such as RK3568 or variations around RK3588. Many of them have been using the HYM8563 I2C RTC chip for about a decade. This device is reasonably cheap, requires few components, consumes very little power and is long proven to work well. Despite its low price, entry-level devices are often lacking it and only have the pads on the board, which is understandable when every dollar counts.  Some such devices include Radxa's E20C and E52C mini routers/versatile servers, which are absolutely awesome devices, which come with either dual-1Gbps or dual-2.5Gbps, feature a USB console so as to always provide a local access, and have a metal enclosure. But they're lacking the RTC, which is quite annoying for a firewall or mini-server, as a power outage always has a painful effect on the dependency chain at home (typically the OS boots faster than the ISP's box and has to start with a bad date). At least once that issue was reported, the products' creator, Tom Cubie (aka @hipboi) acknowledged the problem and suggested that new devices should have it.

Can I do it myself ?

How to proceed with existing devices in the short term ? Isn't it possible to just order the chip and solder it on board ?

One problem with HYM8563 is that it's almost always only found in TSSOP8 format, which means it's a few millimeters wide, with a pitch of 0.65mm, which means that pins are roughly 0.35mm wide with a spacing of 0.3mm between. Actually that's not that difficult to deal with, provided that you have a fine enough soldering iron. The real problem is the components that come around are also of the same scale and very close to each other, as can be seen on the photo of the E52C below (click on the photo to zoom):

The resistors and capacitors are in 0201 format, which is 0.6mm tall by 0.3mm wide, and are very difficult to solder without causing a short circuit. To get a sense of the scale above, the chip is 3mm*3mm. The crystal oscillator is a 32.768 kHz in a flat format that's not easy to find for a hobbyist.

However, the I2C pads (SDA and SCL) are "large enough" and moderately accessible, and there's power on the other side, let's keep that in mind.

Finding a pre-made board

There are various I2C RTC boards available on the net. Most of them are DS1307, and a very nice small one is based on DS3231 with a battery like this one. However, there's no HYM8563 one, and I'd prefer to stay on the same that is referenced in the DTS so that it works out of the box. But I could find the chip alone.

Making a new board instead

Then I started to think whether I could make a board myself based on the chip. Looking at the HYM8563 datasheet above reveals that it's actually not that hard to assemble the few components around. I drew a schematic on by hand (takes one minute vs one hour in Eagle):

I found a few rare occurrences of the chip in SOP8 package, which is easy to deal with, so I could make a PCB with that chip and the 6 components around it. I ordered a pack of 10pcs of that chip, and unfortunately received the tiny TSSOP8 ones instead :-(

But that reminded me that I had some small TSSOP8/SOP8/DIL PCB adapters, which support SOP8 on one side and TSSOP8 on the other side, with the DIL pads in the holes. These are convenient for on-air cabling since pads of both sides are connected together and to the holes:

After all, there were so few components that I could probably solder them directly on that PCB on either side. So let's try.

Bill of materials

Based on the schematic, I'll need this:

• 1 such PCB
  
• 1 HYM8563TS chip
• 1 diode in 0402 format
  
• 2 4.7k resistors in 0402 format
• 1 82pF capacitor
• 1 crystal oscillator
• 1 "large enough" capacitor (I counted about 6mn per 100µF), supporting at least 3.3V
  

 

The secret to avoid shorts when soldering TSSOP chips is to use solder paste. I have some in a syringe that I keep cool in the fridge (otherwise it dries in a few months and is unusable the day you need it):

Assembly steps

As a first step, we'll need to cut a trace on the PCB so as to isolate the VCC input pin from its connection to the IC's pin 8, as we'll want to place the diode there instead. We'll need to keep the resistors connected to the external VCC so that the capacitors doesn't discharge its energy into them when off. Thus we'll cut the trace after the via that connects to the other side. What's nice with these boards is that the pads of both sides correspond to the ones of the other side at the same location, so they're easy to match. The final pinout of the board will look like this:

So let's cut the trace:

Now we're going to place the chip before the diode, because it's already painful enough to solder such small chips, we don't want to be hindered by the diode. The approach for this is to place a very little drop of solder paste over all the pads on each side of the chip. Think in terms of volume, considering that the solder paste is mostly flux that will disappear (the flux will avoid shorts by making it difficult for the solder to make bridges between pins). Count that the resulting volume will be roughly 1/3 of the disposed one. Making a small trail roughly as wide as a pad is a good estimate. Make very sure not to leave any beneath the chip, as it will never melt and will stay them forever, risking to make shorts later. Only cover the pads and areas you can clean later. Once done, just place the chip over the paste:

Now solder everything with the soldering iron, without worrying about the risk of shorts, just focus on aligning the chip as best as possible with the pads, and melt absolutely all the paste. Then check with a magnifier or better, a microscope that everything's OK. With a multi-meter you need to check there's no short between adjacent pins:

Now's time to scratch the right side of the track and to place the diode, with the positive on the right and the negative on the left:

Let's now flip the board to solder the resistors. They will attach to the two bottom left pins, and connect to the beneath pad corresponding to the Vdd pin, which is in fact connected to the positive pin at the bottom right. It has the pleasant advantage of being placed immediately next to the two pins, and close enough to have the resistors directly touching on both ends:

Now let's connect the capacitor between the chip's Vss pin and the top rightmost hole that's connected to the chip's pin 1:

On the other side, the oscillator can be soldered. The pins on the left (when reading the reference) or under the notch are the useful ones. The two other ones on the right are not connected so I could connect them to the pin1 pad, though that will depend on the model since some have integrated capacitors and might not work well when doing so, but I could verify with my multi-meter that there was no capacitor there. In order to solder these pins beneath the component, solder paste is your friend again, being cautious again not to put too much:

We're only left with the capacitor that serves as an energy storage during outages. Ideally you'd use 5.5V super capacitors of 0.1F for several days, or the new 3.8V lithium-based supercaps that have even higher capacities (typically 10F and above). But given that my goal here really to just cover occasional power cuts from the mains, when a power supply dies or when I need to move cables inside my rack, I don't need more than a few minutes. And I did happen to have a 4V/150µF capacitor that perfectly matched my needs (should support 7 to 10mn of outage, and was super flat).

Soldering it is just like for the oscillator above except that it's not easy to use solder paste. The positive terminal (the one with the colored bar) needs to be connected to pin 8 of the chip (the top leftmost here) and the negative to the topmost right  hole. Soldering that one is not too hard, just melt some solder inside the hole. Alternately, using thin wires is OK as well.

Now's time to connect wires and test:

I connected these to another board that I'm using for testing I2C, and ran i2cdetect:

Good, the device appears at address 0x51, so at least it's detected. Now we need to verify that its oscillator is properly ticking. For this we'll have to write the current time to the chip (which appears as rtc1 on this board). It will emit an "invalid argument" because it first tries to read the time which contains a bit "VL" ("Voltage Low") set in the second field indicating the the device lost power since last time it was set. But we can ignore it when writing the date, reading it next will indicate whether it works or not (the time must change):

Perfect, it works! Now's time to replace my testing wires with thin ones, to put all of that into shrink tube to protect it and solder it in the device.

Installation

Let's spot the 4 pads we'll need inside the E52C. First, at the bottom of the board, we'll find the I2C SDA and SCL pins at the bottom on these photos, where we'll solder our SDA/SCL wires (violet and green here). They'll have to pass between the board and the enclosure so they must be very thin, but where I'm passing them, there's enough room:

Next step is to install the module on the other side of the board. We're going to glue it on top of the micro SD card reader with some double-sided tape. The capacitor close to it has both positive (3.3V) and negative and is large enough to support soldering directly to it:

Conclusion

It was fun to make but took me most of the day to build; soldering small components requires delicate manipulations, and dealing with flux and solder paste requires lots of cleaning along the operations. I've made two modules so I still have one extra left. This will allow me to migrate another of my machines to a new one, but I'm impatient to see them produced with the chip already soldered so that I don't have to do this anymore!

Improving A Laser Engraver's Resolution And Accuracy

Baby steps are important

Four years after I wrote about some improvements brought to my Eleksmaker laser engraver, I made quite a lot of progress on multiple fronts.

Laser module

I was regularly annoyed by the too irregular laser beam and finally acquired a NEJE A40640 model that's supposedly 15W optical, made of two diodes and that contains lenses offering a Fast Axis Correction (FAC) to reduce the beam's divergence. The result is an almost square beam that's roughly 60x80 µm by default and can be shrunk to even 60x60 µm at a shorter distance, or be made less than 60 µm wide if made taller.

This constituted the most important improvement because with a poorly shaped beam you can't do any good work. I must say that as of now I think I will never buy again a module without FAC. Think about it, previously if you wanted to cut a circle in wood, half of the circle was completed (e.g. horizontal direction) while the other one was still burning large areas due to the line-shaped beam. Now the same amount of energy is spread in all directions and can be made very narrow.

Air assist

I had been trying various approaches using aquarium pumps to implement some form of air assist to blow the smoke and make a better cut, but these didn't work well. The air flow was made of many irregular pulses and you could hear "puff puff puff" at the output of the laser's head.

I finally decided to order NEJE's air assist accessory for my laser module. Strangely it didn't fit well, it was forcing against the lens' screw. I suspect that the module evolved a little bit since I acquired mine and maybe some dimensions were slightly adjusted on new ones. Nevertheless, I could enlarge the opening of the air assist head so that it fits on my module.

And to get rid of the bad pumps, I finally ordered an AtomStack air pump. The device is really great. It takes 12V input, has a potentiometer to set the air flow speed, and has an output. I just assembled their hose with the one I already had. It further smooths the air flow and now at the output of the module, the flow is super regular and can vary from tiny to quite strong. In practice, most of the time, it's sufficient to set it to 1/4 to 1/3 of the speed in order to blow the smoke away:

 

The results are definitely better, but contrary to what is often seen on ads, it's not on wood that I found the most impressive results, but when engraving images or cutting acrylic. Previously the smoke was causing the beam to diverge a bit, making the result less precise. Now it's super accurate. It's important however to make sure that the piece being worked on doesn't move, because a moving air stream on top of it can make it move (which is another reason for not setting it too strong). That used to be true already for the module's fan anyway. I found that using a few tiny neodymium magnets can be very effective.

Changing the motors' resolution

OK now we're having a nice laser head with much better precision and less disturbances caused by smoke. Isn't that enough ?

In fact I'm using my engraver mostly for PCBs, sometimes for cutting stuff (wood, acrylic), and sometimes to engrave drawings or photos.

For PCBs you do want to have good resolution, otherwise you can't make a track pass between two integrated circuit pins. Or it will touch one side, or be too thin and disappear while etching. With 0.1mm resolution, when you have 0.6mm between two pads of an IC chip, that leaves a single space of 0.1mm on each side, and 0.4mm for the track. Or 0.2mm on each side and 0.2mm for the track. You don't even have an option of 0.15mm each and 0.3mm for the track. And it depends how these are aligned with the motors' steps.

For photos, you generally use Floyd-Steinberg dithering which further reduces the photo's resolution, and when working with 0.1mm dots, that becomes quite visible.

I had been thinking for a long time if it would be possible to find motors with more steps per round. But there was another option that suddenly came to my mind and that I had not yet been considering: what about finding pulleys with less teeth so that it requires more steps to make the same distance ? I searched the net for a few hours and found that the type of belt I'm using is designated as 2GT or GT2 and has a step every 2 mm. My pulleys had 20 teeth and a 5mm axis, and I found others with 16 and even 12. There is a 10-teeth model as well, but only for 4mm axis. So I ordered these, and managed to install the 12-teeth on my motors to replace the 20-teeth one. Here's the photo from the vendor's site:

One assembled, it looks like this (replaced, and with the old one as a comparison):

Doing this requires to adjust the number of steps per mm. It changed from 80 to 133.333 in GRBL's settings, but that's all that needed to be adjusted. I feared that the head would travel slower, but that's not the case. Apparently the speed is more limited by the head's weight and the motors power. However, instead of having a reproducible resolution of 0.1mm, I'm now getting 0.06mm, which precisely is the default size of the beam. Converted to DPI, that's 423 DPI.

This new resolution now allows to export PCBs as images and print them, the result is now good enough. And that's quite convenient because it also means using the same tool for all exports, with the same coordinates system, giving the ability to produce multiple images of various planes, such as the cream plane used to remove varnish and expose solder pads:

In terms of images, this has tremendously improved the result. The dog photo at the bottom is 675x875 pixels and is printed on black-painted aluminum at 0.06mm per dot, resulting in an image of 41x53mm. The result is really impressive, that's 16.6 pixels per mm, or 278 pixels per mm², vs 100 before. That multiplied by 2.78 the pixel density hence the possibilities of nuances in an image.

One problem however is that an image is almost twice as long to print now because there are almost twice as many lines. That was the opportunity for another improvement.

Bidirectional printing

In order to improve print performance, one possibility consists in printing in S form instead of Z, that is, printing even lines from left to right and odd lines from right to left, effectively avoiding a slow return-to-home operation after each line. The software I wrote to convert PNG images to GCODE, png2gcode, already supported such bidirectional printing, but this had always been ugly at high speeds. It was quite visible that there was an offset between each direction. This is not surprising, for three reasons:

• the startup acceleration is not necessarily the same in both directions. However this was addressed long ago with an option to add an acceleration margin to both sides, that I'm typically setting to 3mm ("-A3") so that the beam arrives at full speed on the first pixel to be printed.
  
• micro-stepping is used to control motor positions. Despite using the high-quality TMC 2209 drivers, which take the delivered energy into account to make steps homogenous, it's understandable that the belt's elasticity will not reproduce the exact same position when pulled in one direction or the other, and that it will depend on its tension. Here the belt is quite tight, but tightening it too much can also make it difficult for the motor to make it move in micro-steps.
• the instruction processing time in the micro-controller counts as well.

Till now, png2gcode would offer an option to set an absolute offset for right-to-left printing (that corresponds to the belt tension), and a time-based offset as well for the processing time. However, approximations that had been used till now were hardly reproducible.

The new laser head combined with the new gears was a great opportunity for trying to improve the situation by taking new measurements.

The test consists in printing on anodized aluminum, a rectangle that's 7 pixels high, 40 pixels wide, with a vertical line at 0, 5, 10 and 20 pixels. When printed only left-to-right ("-Mraster-lr"), it's perfectly regular. When printed in bidirectional mode ("-Mraster"), it's visible that every other line is shifted right by one or a few pixels. The same rectangle was printed at speeds of 600, 1200, 2400 and 3000 mm/min from top to bottom. The pixels are 0.12mm wide. The expected pattern is easier to understand on the top and the deformation is increasingly visible as speed increases. The photo had increased contrast to better see the dots:

This allows to see how much variation there is between them, explaining what is dependent on time, and what is fixed. After some calculation and tests, it appeared that the pixels when going right to left had to be shifted left by 0.12mm and delayed by 2.6ms. This delay is converted to mm depending on the travel speed so that in the end it gives only a distance.

With the right adjustments it's possible to align left-to-right and right-to-left and almost double the print speed. Here's a capture of the final results. It's still visible on the large rectangle that there can be around 10 µm variations in positioning because the vertical lines are not always perfectly straight, but that's very hard to notice on the microscope, let alone to the naked eye! The one on the right was printed at 0.06mm per pixel, and there the positioning resolution remains imperceptible.

The image of the lunch at the top of the sky scraper at the bottom of this page is 1206x943 pixels, rendered on a visit card of 72x56 mm, and took approximately 25 minutes to engrave. With unidirectional printing previously it would have taken approximately 45 minutes (it's not exactly twice as long because the return can be a bit faster when not engraving).

Beam narrowing

As can be seen on the test image below, the beam can be made narrower when it's a bit taller. This is important because if the beam is as large as a pixel, then when it sweeps an area as large as a pixel, it has effectively engraved two pixels. The image shows a test pattern with one dot every 0.12mm (the ruler is in millimeters). A zoom on the dots shows they're between 25 and 30 µm wide and approx 100 µm tall:

We can then exploit this principle to consider that the beam will imprint larger than desired and consider this for granted as soon as the beam turns on.

Example: let's say we want to print the green dashed line below (each square is one pixel the size of the beam). The laser dot (in blue) by default will scan from the left of the square to the right, and will effectively span twice its size. The part that was constantly under the beam will have received more energy, and the borders which were only a limited time under the beam will have received less. As can be seen as the beam advances from left to right (line after line), the pattern is reproduced but the contrast is limited.

Now if we take that beam width into account, we can make the beam start to light up later and extinguish it earlier, still providing a shadow around the borders but leaving the intervals totally unexposed. This is more efficiently done by having the dots twice as large as the beam and reducing the beam duration in half, as this would then preserve the intervals.

When taking all that into account, it becomes possible to print photos on painted metal after passing them through Floyd-Steinberg dithering and produce such stunning outputs:

When zooming in macro mode, it's possible to see the dog's hair as 1/16mm dots:

Similarly, a soom at the center/bottom of the lunch photo, zooming on the metallic beam close to a building shows some of the details, then we can zoom further on the beam and it's visible how the gray is obtained by alternating clear and dark lines:

Wrap up

All of this is a question of patience and experimentation. Now I'm able to easily print a photo on metal by using bright black paint and have enough resolution to almost always do it well on the first pass. In the past I had to adjust power, speed, and color conversion to compensate for the risk of too wide pixels ruining everything. That's no longer the case, as can be seen above with direct printing of photos at very high resolution!