Investigate if we can add 8 bits to the cell struct without affecting performance #593

dnkl commented 2021年06月15日 13:09:53 +02:00

The cell struct currently consists of two fields: attrs and wc, where wc is the character it contains, and attrs its attributes (i.e. bold, italic, underline, colors etc).

Most of the attributes are related to ANSI attributes, and are first set in the vt struct's attrs member, and then copied to the cell when a character is printed.

That is, all cell attributes are overwritten when a character is printed.

This becomes a problem for the few attributes that are not related to the ANSI state: currently url and selected.

The selected bits informs the renderer that the cell is selected (by the user) and should be highlighted as such. Thus, if the user has selected a region of text, and cells within that region is updated, those cells "lose" their selected state. We are currently working around this by walking all selected cells and updating their selected bits just before rendering.

Things would become much simpler if we could separate the ANSI state from cell persistent state. For performance reasons, we cannot just split the attributes struct, as that would require more instructions when copying the attributes when printing a character.

But perhaps we can add an uint8_t to the cell struct? This new bitfield would contain state that needs to be persistent across cell writes. It would of course increase foot's memory usage, with ~8% (13 vs. 12 bytes). It may also affect our cache usage in a negative way.

The `cell` struct currently consists of two fields: `attrs` and `wc`, where `wc` is the character it contains, and `attrs` its attributes (i.e. **bold**, _italic_, underline, colors etc). Most of the attributes are related to ANSI attributes, and are first set in the `vt` struct's `attrs` member, and then **copied** to the cell when a character is printed. That is, **all** cell attributes are **overwritten** when a character is printed. This becomes a problem for the few attributes that are **not** related to the ANSI state: currently `url` and `selected`. The `selected` bits informs the renderer that the cell is selected (by the user) and should be highlighted as such. Thus, if the user has selected a region of text, and cells within that region is updated, those cells "lose" their selected state. We are currently working around this by walking all selected cells and updating their `selected` bits just before rendering. Things would become much simpler if we could separate the ANSI state from cell persistent state. For performance reasons, we cannot just split the attributes struct, as that would require **more** instructions when copying the attributes when printing a character. But perhaps we can add an `uint8_t` to the cell struct? This new bitfield would contain state that needs to be persistent across cell writes. It would of course increase foot's memory usage, with ~8% (13 vs. 12 bytes). It may also affect our cache usage in a negative way.

craigbarnes commented 2021年06月15日 14:52:35 +02:00

But perhaps we can add an uint8_t to the cell struct?
...
It would of course increase foot's memory usage, with ~8% (13 vs. 12 bytes)

I think adding a uint8_t member would increase sizeof(struct cell) from 12 to 16 bytes. _Alignof(struct cell) is 4, so the compiler would have to add 3 bytes of padding.

> But perhaps we can add an `uint8_t` to the cell struct? > ... > It would of course increase foot's memory usage, with ~8% (13 vs. 12 bytes) I think adding a `uint8_t` member would increase `sizeof(struct cell)` from 12 to 16 bytes. `_Alignof(struct cell)` is 4, so the compiler would have to add 3 bytes of padding.

dnkl commented 2021年06月15日 15:39:13 +02:00

Ah, right, of course. We could always pack it.

But, and I didn't mention this in the description above, a 13-byte struct means we'll be doing unaligned memory accesses. Not sure how much impact that will have. Slower, for sure, but by how much? I guess that's part of the investigation :)

We get by pretty ok with the current state bits. But #592 is hard to do without persistent cell state.

Ah, right, of course. We could always pack it. But, and I didn't mention this in the description above, a 13-byte struct means we'll be doing unaligned memory accesses. Not sure how much impact that will have. Slower, for sure, but by how much? I guess that's part of the investigation :) We get by pretty ok with the current state bits. But https://codeberg.org/dnkl/foot/pulls/592 is hard to do without persistent cell state.

NRK commented 2022年07月01日 11:28:38 +02:00

13-byte struct means we'll be doing unaligned memory accesses.

Depending on what you're doing, you can maybe get away with a "pool" instead.

struct cell_pool {
 struct cell cells[5]; // 60 bytes
 uint32_t flags; // 4 bytes - each cell gets to have 6 bits.
};

This will fit cozily into 64 bytes without needing to do any forced packing.

Disclaimer: I'm not really familiar with foot's codebase, so feel free to ignore if what I said doesn't apply.

> 13-byte struct means we'll be doing unaligned memory accesses. Depending on what you're doing, you can maybe get away with a "pool" instead. ```c struct cell_pool { struct cell cells[5]; // 60 bytes uint32_t flags; // 4 bytes - each cell gets to have 6 bits. }; ``` This will fit cozily into 64 bytes without needing to do any forced packing. **Disclaimer**: I'm not really familiar with foot's codebase, so feel free to ignore if what I said doesn't apply.

mildred commented 2023年01月18日 09:54:08 +01:00

The selected bits informs the renderer that the cell is selected (by the user) and should be highlighted as such. Thus, if the user has selected a region of text, and cells within that region is updated, those cells "lose" their selected state. We are currently working around this by walking all selected cells and updating their selected bits just before rendering.

Others terminals (gnome-terminal) removes any selection if the text within the selection is updated. I believe this could be a legitimate behaviour because then you don't know what text you copied. The problem arise when there is a constant changing text and you want to copy some of it.

> The selected bits informs the renderer that the cell is selected (by the user) and should be highlighted as such. Thus, if the user has selected a region of text, and cells within that region is updated, those cells "lose" their selected state. We are currently working around this by walking all selected cells and updating their selected bits just before rendering. Others terminals (gnome-terminal) removes any selection if the text within the selection is updated. I believe this could be a legitimate behaviour because then you don't know what text you copied. The problem arise when there is a constant changing text and you want to copy some of it.