Structures should not store large structures

[GermanAizek]

Structures should not store large structures, structures larger than 64 bytes should be converted to 8 byte pointer.

Modern CPUs rely heavily on caching to speed up memory access. When a large struct is loaded into the CPU cache, it occupies a significant portion of the cache line. If you only need to access a small part of that struct, or if the relevant data is scattered across many large structs, it can lead to more cache misses and slower performance. By storing pointers, the parent struct is small and can be more easily kept within the CPU cache. The actual data pointed to can be fetched only when needed, potentially leading to better cache utilization for frequently accessed data.

Example:

Unoptimized structure

struct A {
  (size 56 bytes)
   struct B {
     (size 256 bytes)
   }
} objA;

sizeof(objA); // 312 bytes (5 CPU cacheline)

Optimized CPU Cache-like structure

struct B {
  (size 256 bytes)
} objptrB;

struct A {
  (size 56 bytes)
  objptrB (size 8 bytes)
} objA;

sizeof(objA); // 64 bytes (1 CPU cacheline)

[HaplessIdiot]

Yes I love the idea of moving to 512 byte chunks to optimize for cache! This is great please if you can try and find examples in the code we can clean up. I can help rewrite in this format quicker if you can find me and others the offending spots you find it in. This is the largest codebase ive tried to contribute to a line number would be killer if you can get it.

[roryyamm]

Wouldn't this break ABI compatibility in some horrifying way?

[GermanAizek]

Wouldn't this break ABI compatibility in some horrifying way?

To really make X server better, we'll have to break ABI anyway. Otherwise, what's the point fork if it's the same as Xorg Foundation.

[metux]

That would require much more allocations (and additional bookkeeping logic). And we need to be very careful about not breaking ABI.

[GermanAizek]

That would require much more allocations (and additional bookkeeping logic). And we need to be very careful about not breaking ABI.

in theory, I can just give you changes that don't break ABI. And for yourself and those who are interested in more optimized but poorly compatible X server with old software, make separate fork, name it roughly so fastx11 or x11fast and whoever needs it will compile for themselves.

I don't have enough old X software, it's more important for me to reduce system-wide CPU cache misses on my workstation server cluster.

I must say right away that cluster on Gentoo, but they are developing and contributing with Debian.

[stefan11111]

@GermanAizek
Have you benchmarked and found that this speeds things up?
Doing thinks this adds more indirection and memory usage.
Even if abi weren't a problem, this only speeds things up if you only access the parts of that structure except the pointer. If you need the data that is behind that pointer, the this patch slows things down. Not to mention what happens when you want to copy this struct or allocate a new one. Think how large arrays are almost always preferable to linked lists.
I'd want to see some benchmarks that show improvements over the regular structs.

As for the abi problem, like I said on your other pr, if we become abi-incompatible with Xorg, then nvidia will have to
chose to build against either Xlibre or Xorg, and I think they will chose Xorg.

[GermanAizek]

@GermanAizek Have you benchmarked and found that this speeds things up? Doing thinks this adds more indirection and memory usage.

Alan Cooper, he said that there are few performance tests in the x server and there is only x11test.

Good option is to run perf profiler and valgrind.

@stefan11111,
I have to prove it every time. For the sake of interest, you can ask the AI a question or Google it. Many sources describe this optimization method, but because they now like to neglect optimization in favor of developing functionality, devs rely on compilers. There are good books from Barry Brey that describes how modern processor architecture works.

This kind of optimization just physically couldn't be worse for 64-bit CPU (most common arch).

My favorite computer science writer:

https://archive.org/details/ref-book-1-barry-b.-brey-the-intel-microprocessors-architecture-programming-interfacing-phi-6th/mode/2up?view=theater&ui=embed&wrapper=false

Best real linux kernel example align structures for 64-bit and reduce size structures for cache-like:

https://www.phoronix.com/news/Linux-6.8-Networking

https://www.youtube.com/watch?v=qo1FFNUVB-Q

My alignment PRs with benchmarks:

https://code.videolan.org/videolan/dav1d/-/merge_requests/1788

ggml-org/llama.cpp#7267

[GermanAizek]

@stefan11111
If better benchmark is created than old X11test, you can find out the percentage very accurately. But I guarantee that this will always be a positive thing, since C/C++/C# compilers do not reorganize fields and sizes of structures unless the developer forcibly requests it using keyword packed.
But packed can slow down work with CPU cache, on contrary, since compiler compresses for the smallest possible size structures, and this keyword was focused on IoT devices, where performance can be neglected in favor of saving memory.

[stefan11111]

@stefan11111 If better benchmark is created than old X11test, you can find out the percentage very accurately. But I guarantee that this will always be a positive thing, since C/C++/C# compilers do not reorganize fields and sizes of structures unless the developer forcibly requests it using keyword packed. But packed can slow down work with CPU cache, on contrary, since compiler compresses for the smallest possible size structures, and this keyword was focused on IoT devices, where performance can be neglected in favor of saving memory.

It is not always a good thing to replace large structs with pointers.
Think of this:

typedef struct {
    char arr[512];
} large_1_t;

typedef struct {
    char arr[248];
    void *rest;
} large_2_t;

large_1_t *copy_1(large_1_t *src)
{
    large_1_t *ret;
    ret = malloc(sizeof(*src));
    if (!ret) {
        return NULL;
    }
    memcpy(ret, src, sizeof(*src));
    return ret;
}

large_2_t *copy_2(large_2_t *src)
{
    large_2_t *ret;
    ret = malloc(sizeof(*src));
    if (!ret) {
        return NULL;
    }
    ret->rest = malloc (512 - 248);
    if (!ret->rest)) {
        free(ret);
        return NULL;
    }
    memcpy(ret->arr, src->arr, sizeof(src->arr));
    memcpy(ret->rest, src->rest, 512 - 248);
    return ret;
}

The second one is way slower that the first one.
This kind of 'optimization' can't be done blindly.

[GermanAizek]

It is not always a good thing to replace large structs with pointers.

The first structure should be 64 bytes, it refers, if necessary, to a large one, or vice versa, frequently used fields refers, if necessary, to a small 64 byte one.

Also, when accessing, spending CPU cycles on dereferencing ptr, if there is frequent access, it can do harm.

By default, prefer nested structures (by value). It's easier, safer, and often faster due to data locality.

Go to the pointers if you have a clear reason:

• You need to share data between objects
• The object is very large and it is expensive to copy it
• You need polymorphism
• The relationship between the objects is optional

In other words, it is better to use a pointer for rarely used structures, but divide the frequently used ones into structures that are multiples of 64 bytes. As close to size 64 bytes as possible.

[GermanAizek]

This kind of 'optimization' can't be done blindly.

If you're talking about this issue, it won't work blindly, like aligning structures. That's why I created future PR.

[GermanAizek]

for these changes, which share structures with pointer access, it is desirable to have a good benchmark aka new X11Test.

[GermanAizek]

@stefan11111,
I renamed this PR X11Libre/xserver#14
to avoid confusion with this issue in the future.

[callmetango]

Hello @GermanAizek,

thank you for reporting the issue. Could you please update the description using the template given in #131 ?

Please add your content in the template fields enclosed with {{ and }} and remove the curly braces.

Could you please mark the checkboxes in the Extra fields section too by replacing the space with an x?

Thanks for your help.

[callmetango]

@GermanAizek Could you please please pay special attention to the aspect of "API/ABI stability" in the "Additional Information" section when updating the issue description? This must be very well thought out.

[callmetango]

I'm moving this to X11Libre Ideas · Discussions · GitHub since there are still some open questions. Also the real value should be shown by numbers and outweight the risk of breaking things significantly.

[callmetango]

This will be closed because the reporter did not respond. Please comment on this of you feel the need to reopen this discussion.