Generating GUI keys from return addresses
Lately I have gone down the rabbit hole of immediate-mode GUI, and decided to write my own imgui code for my own projects that does layout computations and issues draw commands to the renderer. In the process I figured out a very nice way to generate keys for persistent state that I have not seen used anywhere and wanted to share it.
TL;DR: if your widgets are functions and you manage to make your compiler never inline them, you can use the return address as a key for storing state across frames.
What is immediate-mode GUI?
Immediate-mode GUI, or imgui for short, is a style of writing GUI code where the user specifies each GUI element to draw directly inside the render loop, every frame, using an immediate-mode API. Put simply, the UI view/layout is recomputed every frame, dynamically, based on the user's widget specifications. Imgui code tends to look something like this:
{ // Inside the render loop
bool pressed = button("my button label");
if pressed {
do_something_cool();
}
}
This is a simplified version, because you still need to pass layout information (height, width, color...) to your button draw function somehow, but I won't be talking about that in this article.
This style of writing GUI code was originally demonstrated by Casey Muratori and later got popularized by open source libraries such as Dear ImGui. The benefit of this style of coding, as opposed to traditional retained mode (where the UI layout is mostly static/pre-allocated and mutated upon user interaction), is that your UI looks and feels reactive and dynamic, it also tends to render correctly with no visual bugs.
The drawback is that you are recomputing your UI layout every frame, but this isn't an issue for modern processors, they are so fast that even a layout of more than 1000 widgets can be computed in under a milliseconds, that is if you code it correctly and don't make your processor chase data pointers spread all over memory.
Why widgets need keys
Some widgets data can't just be recomputed it must be stored across frames for the widget to behave correctly. A checkbox, for example, needs to keep track of whether it's checked or not, a scroll region needs to save the scroll progress, and so on. The responsibility of allocating and preserving the state for some of these widgets can be placed on the user. The checkbox, only needs a boolean variable that outlives the frame lifetime, and the user can allocate it outside that scope and pass it as pointer to the checkbox function.
// global namespace
bool is_checkbox_checked = false;
...
{ // Inside the render loop
checkbox("check me", &is_checkbox_checked);
if is_checkbox_checked {
make_user_happy();
}
}
However, in some cases it's too cumbersome for the user to keep track of the widget state, especially when it serves them no purpose. In the case of a scroll region the user has no use for the scroll progress or the size of the content that has been clipped from view. It's also more convenient for the GUI code to manage this state internally and have access to it whenever. To do this we need a way to correlate every widget call site with its state across frames. The most obvious solution is a key-value lookup table or a hashmap that stores the widget state and allows for quick access to it through unique keys.
struct UiState {
float2 scroll_view;
float2 scroll_offset;
float animation_rate;
// you can aggregate more properties
// that need to be saved inside this struct
};
Hashmap<UiState> state_map;
function widget(...){
WidgetKey key = ?? ; // what do i use for this ?
widget_state = state_map.get(key);
// remaining widget logic code
}
NOTE: I use
...to omit function parameters and unnecessary details.
OK, the state map is in place. Now, how do I get unique keys? Well, let's look at the existing solutions.
Common ways to generate keys
1. Let the user handle and supply keys
One way to do it is to just ask the user to come up with some keying mechanism and pass it to the function. This, however, is a very bad choice, because:
- The user needs to put in extra mental effort to produce these keys.
- The correctness of your code now relies on the user doing everything right with no mistakes (which is usually not the case).
- It's just not a fun experience for the user at all, and software should be FUN.
So overall not a good solution. Moving on.
2. Per-frame counter
Another naive solution that comes to mind early is using a serial integer as the key: say we keep track of the widget count and use it as the widget key.
function widget(...){
widget_count = widget_count + 1;
WidgetKey key = widget_count;
widget_state = state_map.get(key);
// remaining widget code
...
}
This works fine, plus in case of a hashmap collision we only need to compare integers to find the value, not very costly in terms of performance. However, this solution breaks as soon as a layout change happens. Consider the following example:
bool agrees_to_tos = false;
{ // render loop
checkbox("I agree to the terms of service", &agrees_to_tos);
if agrees_to_tos {
if button("Start") {
launch_program();
}
}
if button("Exit") {
exit_program();
}
}
Now what key value does the Exit button get? Well, that depends: if agrees_to_tos is false the key value is 2, otherwise it's 3 and the Start button gets the key value 2.
And therefore both buttons access the wrong state and your UI starts looking weird.
3. Hashing string labels
This one is pretty robust in most cases. It consists of asking the user for a string label that you then pass to a fast hash function to produce a key.
// function definition
function widget(string_key,...) {
widget_state = state_map.get(compute_hash(string_key));
// rest of the widget code
}
{ // render loop
widget("my 1st widget");
widget("my 2nd widget");
widget("my 3rd widget");
...
}
This solution isn't affected by layout changes, also Dear ImGui uses a strategy similar to this one and it works. There are however some caveats to keep in mind. First, it is again the responsibility of the user to give each widget an original unique string key (and I certainly don't have that ability just look at what I did up there in the previous example). Another issue is loops. Consider the following example:
for i = 0 to 100 {
list_item("list_item", some_list_data[i]);
}
Can you see the problem? All 100 list_items have the same string key and therefore the same state, so you click one and you end up clicking all of them. Your UI is broken, your software is buggy, and your users are unhappy :(
You might think that loops are not really necessary in UI code, but trust me they are. Just look at your email application: how do you think it displays the list of emails in your inbox?
In cases like these you just can't use a static string as a key, but instead need to dynamically generate them on the fly with information unique to the loop, and an obvious one is the loop index i.
for i = 0 to 100 {
// now each item gets its own unique key.
list_item(format("list_item#%d", i), some_data_to_display[i]);
}
One more issue arises when composing widgets. Consider the following situation: you want to refactor some common widget code into a single function that you can reuse so you did something like this:
void big_widget(){
widget_a("BIG_A",...);
widget_b();
if(widget_c("BIG_C",...)){
widget_d();
}
}
...
{ // inside your frame loop
big_widget();
big_widget();
}
The problem now is that the widgets inside big_widget are using the same state every time you call that function.
You can solve this by passing more information to big_widget like a prefix string that gets concatenated with the widget key string.
void big_widget(prefix){
widget_a(CONCAT(prefix,"BIG_A"),...);
widget_b();
if(widget_c(CONCAT(prefix,"BIG_C"),...)){
widget_d();
}
}
...
{ // inside your frame loop
big_widget("Big 1");
big_widget("Big 2");
}
But overall this remains a good robust keying strategy. I, however, don't quite like it, coming up with string labels requires some engagement and thinking on my side to keep the labels unique, and I'm honestly too lazy for this. Luckily for me, there is another unique number that just gets passed automatically to every function at the machine code level and that I can derive a key from. And that number is called the return address of the function.
Quick aside: if you need a quick explanation of how return addresses work, I wrote a brief explanation at the end of this post.
Return addresses as keys
So when writing imgui code you tend to declare your widget building code as functions, as we have done so far. So to get a key you just need to get the return address that the processor saved before jumping to your function.
How can you do that? Well, it depends on your programming language's features. If you are using a systems programming language, there is possibly a way.
And if your language allows you to just write raw assembly then you can absolutely do this, however in most popular systems languages writing assembly is not necessary.
But if you're using some interpreted language like Python, or some VM-imprisoned language like Java, I am not sure it's possible.
In C/C++ there is a non-standard GCC/Clang intrinsic __builtin_return_address that you can use:
void button(...) {
void* addr = __builtin_return_address(0); // on MSVC there is _ReturnAddress() from <intrin.h>
uint64_t key = (uint64_t)addr;
UiState button_state = get_or_make_state(key);
// The rest of your logic.
}
In Zig you can use the @returnAddress function:
fn button(...) void {
const key = @returnAddress();
const button_state = get_or_make_state(key);
// The rest of your logic.
}
In Rust there is currently an unstable std::intrinsics function called return_address that says it can do this,
but I have never tried it.
However, there is a caveat here: when shipping code your compiler might choose to inline your functions as an optimization.
Inlining a function just copies its code into the caller's code, and this way it avoids emitting a call instruction.
If this were to happen, your function's return address becomes the caller's return address and is no longer guaranteed to be unique. Consider this:
void show_ui(...) {
// some ui code
button("Prev");
...
button("Next");
}
If these 2 button function calls get inlined they end up with the same return address, which is the return address of show_ui, and consequently the same key and the same state.
And this breaks your UI logic.
The easy way to solve this is to tell your compiler to never inline your functions.
In C/C++ use the noinline attribute:
__attribute__((noinline)) void button(...) { //NOTE: if you are using the Microsoft MSVC toolchain it's __declspec(noinline)
void* addr = __builtin_return_address(0);
uint64_t key = (uint64_t)addr;
UiState button_state = get_or_make_state(key);
// The rest of your logic.
}
In Zig use the noinline keyword:
noinline fn button(...) void {
const key = @returnAddress();
// The rest of your logic.
}
In Rust use this to disable inlining:
#[inline(never)]
fn button(...) {
// The rest of your button logic.
}
Perfect, that solves the inlining problem. Now our keys are guaranteed to be unique, since the call instruction is also unique in the machine code,
and best of all they are generated without any mental effort from the user, and since they fit into a 64-bit integer we only pay for an integer comparison upon collision.
Now, it's not all sunshine and rainbows; there's still more to do to make this robust.
But what about loops?
Widgets in loops
Consider the following code:
{ // ui code
for(int i = 0; i < 10; i+=1){
checkbox(...);
}
}
All our checkboxes will get the same return address and therefore the same key. This is bad, but we can fix it. We will just OR a loop index into the upper bits of the return address. You see, while our function return address is a 64-bit value (or 32-bit on 32-bit processors), only the lower bits tend to change in return addresses. That's because when your program's instructions region is mapped to memory it occupies a single contiguous block of memory, so addresses tend to be serial. Also, this contiguous block of memory is often not that big, usually less than 100 MiB, so really the upper bits stay kind of constant in the return address and don't change at all throughout your program's execution, so it's safe to replace them with actually important information like our loop index.
Let's implement our UI key logic.
#define RET_ADDRESS __builtin_return_address(0)
#define UI_KEY_ADDR_BITS 32
#define UI_KEY_MASK ((1ull << UI_KEY_ADDR_BITS) - 1)
#define INVALID_ADDR 0
struct UiKey{
UiKey(int32_t loop_index):addr_(0), loop_index_(loop_index) {}
void update(void* addr) {
uint64_t uaddr = (uint64_t)addr;
if(this->addr_ == INVALID_ADDR) this->addr_ = uaddr & UI_KEY_MASK;
}
uint64_t value() const {
uint64_t v = (uint64_t) this->loop_index_;
v = v << UI_KEY_ADDR_BITS;
v = v | this->addr_;
return v;
}
private:
uint64_t addr_ = INVALID_ADDR;
int32_t loop_index_ = 0;
};
__attribute__((noinline)) void checkbox(UiKey key,...) {
key.update(RET_ADDRESS);
UiState checkbox_state = get_or_make_state(key.value());
// remaining checkbox building code
...
}
// somewhere in our ui code
{
for(int i = 0; i < 10; i+=1){
checkbox({i},...);
}
}
Impressive, very nice, but what about composing widgets?
Composing widgets
It is inevitable that you would want to reuse your simple widgets to compose more complex widgets, for example a counter made of a numeric input field and the increment/decrement buttons. Well, since these 3 widgets are stateful you would need 3 different keys for this composition to work, and a function only has one return address, so how do we solve this? The answer is the same as before: reserve more upper bits and generate the keys at the start of the function.
NOTE: Any reusable widget code must also be a non-inlined function for this to work.
#define RET_ADDRESS __builtin_return_address(0)
#define UI_KEY_ADDR_BITS 32
#define UI_KEY_CHILD_BITS 4 /* 16 children is more than enough, this leaves us with 28 address bits */
#define UI_KEY_MASK ((1ull << (UI_KEY_ADDR_BITS - UI_KEY_CHILD_BITS)) - 1)
#define INVALID_ADDR 0
struct UiKey{
UiKey():addr_(0), loop_index_(0), child_id_(0) {}
UiKey(int32_t loop_index):addr_(0), loop_index_(loop_index), child_id_(0) {}
UiKey(uint64_t addr, int32_t loop_index, int32_t child_id):addr_(addr), loop_index_(loop_index), child_id_(child_id) {}
void update(void* addr) {
uint64_t uaddr = (uint64_t)addr;
if(this->addr_ == INVALID_ADDR) this->addr_ = (uaddr & UI_KEY_MASK);
}
/* New */
UiKey new_child() {
this->child_id_ = (this->child_id_ + 1) & ((1 << UI_KEY_CHILD_BITS) - 1);
UiKey new_key(this->addr_, this->loop_index_, this->child_id_);
return new_key;
}
uint64_t value() const {
uint64_t v = (uint64_t) this->loop_index_;
v = v << UI_KEY_CHILD_BITS;
v = v | this->child_id_;
v = v << (UI_KEY_ADDR_BITS - UI_KEY_CHILD_BITS);
v = v | this->addr_;
return v;
}
private:
uint64_t addr_ = INVALID_ADDR;
int32_t loop_index_ = 0;
int32_t child_id_ = 0;
};
__attribute__((noinline)) void counter(UiKey key,const char* title,...) {
key.update(RET_ADDRESS);
UiKey inc_btn_key = key.new_child();
UiKey dec_btn_key = key.new_child();
UiKey input_key = key.new_child();
start_row();
{
// Assume button and input_numeric widgets are already defined somewhere
button(dec_btn_key, "-");
input_numeric(input_key, &buffer);
button(inc_btn_key, "+");
}
end_row();
}
// somewhere in our ui code
{
counter({}, "Counter A");
counter({}, "Counter B");
...
}Demo
Time for a demonstration, the UI in the following video is built entirely with the concept of using the return address as a keying mechanism.
Limitations
Now, of course, this technique does have a limitation: in general you will find friction when trying to compose complex widgets into bigger, reusable, more complex widgets.
I would make the claim, however, that composing complex widgets together is not a sign of good UI, as good UI in my opinion tends to be more visually simple and easy on the eye.
You also need to remember to declare your functions with the noinline attribute, you can make your developer experience better by adding checks for key uniqueness in debug mode.
Side notes
-
The
UiKeystruct fields can be packed into a 64-bit integer to reduce its memory footprint, and depending on your programming language's ergonomics they can still be accessed easily. In Zig for example you can do this:pub const UiKey = packed struct(u64) { ret_addr: u28 = 0, child_id: u4 = 0, loop_index: u32 = 0, }; -
How you reserve the bits is up to you, the most important decision is the number of return address bits, and that should be big enough so as not to lose call site information.
Wrapping up
So that is the whole idea: derive your widget keys from the function return address.
You get keys that cost the user no mental effort at all, that survive layout changes, that fit in a single 64-bit integer so a hashmap collision only costs you an integer comparison,
and that need nothing from your language beyond an intrinsic most systems languages already hand you.
The price is three things to keep in mind: mark your widget functions noinline, reserve some upper bits for a loop index when you build widgets in a loop,
and accept that complex widget composition is where the scheme breaks down.
I have been using this in my own projects and it has been a far nicer experience than naming every stateful widget by hand. This approach might not be the best for shipping an open source library, but for my case it does the job perfectly. If you end up trying it in a language I didn't cover here, or you find a nicer way around the composition limit, I would be glad to hear about it.
Appendix: a quick primer on return addresses
This is a quick explanation of how return addresses work at the machine code level, for anyone who wants to see the ground underneath the trick above.
When you compile a program's source code, the compiler generates machine code for the target processor. This machine code is just a contiguous block of bit patterns that the processor interprets as the instructions it needs to run the specified logic of your program.
Trying to identify bit patterns is very hard for us humans, and that's where assembly comes in: assembly maps these bit patterns to mnemonics that are easy to read and understand. We tend to use these mnemonics as names for the CPU instructions, and for the most part they describe very well what the CPU does.
add: add 2 numbers.sub: subtract 2 numbers.mov: copy a value between memory and registers.jmp: jump to a different instruction in the machine code.
The one instruction we care about here is the jmp instruction: it tells the processor to jump to another instruction in the machine code.
This could be the instruction right after it, or one somewhere far from the current instruction; the jmp specifies exactly where, using the address of the instruction it wants the processor to jump to.
What is an address, you might ask? You see, the machine code is usually loaded into your computer's memory, and each byte gets its own address, which is just a number counted from the beginning of the computer memory, with that beginning having an address of 0.
You just add 1 to the address to get the address of the next byte.
Now usually your computer executes instructions in serial order, moving from one instruction to the one after it, however for some logic the serial order doesn't work.
For example, if you have an if branch, then depending on the condition your computer needs to execute either instruction A or instruction B.
This is where jmp instructions comes in handy.
Functions are another reason jmps are useful, because your processor needs to jump to that function's code, execute it, and then come back.
Jumping to a function, however, doesn't use the jmp instruction, because the processor needs to remember where to come back to. It instead uses another
instruction, usually named call, that saves the return address before jumping to the function's code. This return address is simply the address of the instruction immediately after the function call.
This is all we needed to understand the keying trick, so we will wrap this tangent up here.
For more information about the subject checkout this amazing blog post.
-Imad