OSDev.org

embryo wrote:

Brendan wrote:Alternatively, maybe you write your code to handle misaligned arrays; with an initial loop to handle from the start of the array up to the first page boundary, then a middle loop for the majority of the array (that is page aligned), then another loop for the (partially used) last page of the array.

It works for big arrays, but when predictor catches the direction of a sequential memory access, wouldn't it preload next page when memory reads hit somewhere close to a predictor's threshold? Then only initial loop seems as viable.

embryo wrote:But if there is an opportunity to work with data in chunks (like usage of cached data in more than one operation), then predictor will be unable to preload the data because memory read pattern tends to exhibit locality instead of sequentiality. Here we need to use prefetch instruction. And as I understand it should be executed at least twice to initiate predictor's preload action, right?

embryo wrote:

Brendan wrote:Ideally, the length of an instruction's opcode should depend on how often its used - the most frequently used instructions should have the shortest opcodes possible.

But if instruction read bandwidth is measured in gygabytes per second then it is possible to have just a bit more complex decoder and forget about instruction length. Or there are situation when processor stalls because of empty instruction pipeline?

embryo wrote:As I see it an instruction cache is independent and instruction read should have more priority than data read, so it is hardly possible to stall a processor because of high data load.

embryo wrote:

Brendan wrote:Once we complete the transition to UEFI real mode will become removable

I suppose such transition will take us so far as 2030-s or even later. What has became removable in last 15-20 years? Or in 35 years?

embryo wrote:

Brendan wrote:If an OS doesn't use paging, then it won't suffer from TLB misses at all; but will suffer from other problems (related to efficient memory management)

What kind of problems of memory management (without virtual memory) you can think of in case of managed code?

embryo wrote:range [ecx], [ecx+0xaaaa]; this range also will be used by following loop
...; some loop instructions

range [ecx] ; cycle 1, load [ecx]
mov eax, [ecx] ; cycle 2 - stalls for 98 more.
; cycle 100

mov eax, [ecx] ; cycle 1 - stalls for 99 more.
; cycle 100

On task switch system need to push the buffers on a stack just like it now pushes content of 16*256+16*128+16*64+[other registers] bits of all registers. It means we can have something like one kilobyte for mentioned buffers without serious performance degradation.

mwait; some kind of synchronization between processor and memory controller

some other x86 instructions, that expect quick memory access

fetches memory range [eax]-[eax+0xbbbbb] into L1 cache

And, of course, hardware operations should be more transparent to help us create effective programs, that are not spoiled by some unpredictable hardware behavior.

Brendan wrote:If "predictor" is the hardware prefetcher's steam detector (which needs a few cache misses to get started, and where the hardware prefetcher stops every time it reaches a page boundary); then either you're relying on hardware prefetching and shouldn't do software prefetching; or you're relying on software prefetching and there shouldn't be any cache misses left for the hardware prefetcher to detect.

Brendan wrote:To force the TLB to be loaded you need...

Brendan wrote:There are many situations when processor stalls because of empty instruction pipeline. A simple example is a branch mis-prediction.

Improving instruction density (getting more instructions in less RAM) improves the time it takes to recover from stalls and also improves the number of instructions you can fit in caches.

Brendan wrote:For an instruction to complete you need the instruction and its data. Having one and not the other doesn't help, regardless of whether you have the instruction and not the data, or the data and not the instruction. If you make instruction fetch higher priority, then you'd just spend more time stalled waiting for data.

Brendan wrote:In the last 20 years; PIC got replaced with IO APIC, PIT got replaced with HPET, ISA got replaced with PCI, serial and parallel and floppy got replaced with USB, PATA got replaced by AHCI, FPU/MMX/3DNow got replaced by SSE, protected mode got replaced by long mode, plain 32-bit paging got replaced by PAE which got replaced by long mode, hardware task switching got replaced by nothing, several exceptions (coprocessor segment overrun, bound, overflow) got deprecated, etc.

Brendan wrote:

embryo wrote:What kind of problems of memory management (without virtual memory) you can think of in case of managed code?

Dealing with physical address space fragmentation, supporting memory mapped files efficiently, supporting shared memory efficiently, supporting swap space efficiently, doing various "copy on write" tricks efficiently, etc. All of these things are more efficient because paging provides an extra layer of indirection.

Brendan wrote:Managed code could also provide an extra layer of indirection in software

Brendan wrote:it'd have the same issues as paging (e.g. cache misses caused by a "virtual reference to physical address" lookup in managed code, that's equivalent to a TLB miss) but it'd be slower than the "already hardware accelerated" equivalent.

Brendan wrote:More likely is that managed code wouldn't add the extra layer of indirection and wouldn't get any of the advantages, and then the developers would try to pretend everything is OK by publishing research papers showing the results of carefully selected (and heavily biased/misleading) micro-benchmarks in an attempt to hide the fact that the OS sucks for all practical purposes.

Combuster wrote:

embryo wrote:range [ecx], [ecx+0xaaaa]; this range also will be used by following loop
...; some loop instructions

A cache miss will still prevent the first instruction of the loop from executing regardless of the preceding range statement, possibly out-of-ordering the next item in the loop and firing an automatic loading sequence. The absence of a cache miss will make the process slower due to decoding overhead.

Combuster wrote:

mwait; some kind of synchronization between processor and memory controller

The whole advantage with out-of-order execution is that instructions can be executed while others are waiting. Any form of synchronisation is slow, and useless baggage if there's no cache miss.

Combuster wrote:

fetches memory range [eax]-[eax+0xbbbbb] into L1 cache

Oops, the state-of-the-art L1 cache isn't even 5% of that.

Combuster wrote:Hardware is less transparent to save us time from dealing with details and create effective programs instead.

Owen wrote:Brendan's cache flush instructions are pretty much useless - flushes have no effect on non-dirty lines and on dirty lines the data remains resident in cache (it just gets pushed out to RAM).

Owen wrote:Perhaps he meant clean, which empties the cache line.

Owen wrote:Regardless, they're an enormous waste of cache traffic - the processor will successfully do least-recently-used replacement anyway. If you are working on such large quantities of memory that the cache effects are important, and you can avoid reading or writing a location twice, just use a damn non-temporal read/write instruction.

Owen wrote:Theres a reason why processor manufacturers don't tell you about the exact predictor setup of a processor and change it - it's because they, after all, want to be able to improve their processors from generation to generation. Or, even more importantly, they don't want to get locked into an inappropriate predictor design. Hell, consider, say, the Qualcomm Snapdragon 810 with 4x Cortex-A53 and 4x Cortex-A57. The Cortex-A53 is a little, in-order processor; the A57 is a big out-of-order machine. They have completely different designs, different performance characteristics, and different performance points.

Brendan wrote:Hi,

Owen wrote:Brendan's cache flush instructions are pretty much useless - flushes have no effect on non-dirty lines and on dirty lines the data remains resident in cache (it just gets pushed out to RAM).

According to Intel, the CLFLUSH instruction:
"Invalidates the cache line that contains the linear address specified with the source operand from all levels of the processor cache hierarchy (data and instruction). The invalidation is broadcast throughout the cache coherence domain. If, at any level of the cache hierarchy, the line is inconsistent with memory (dirty) it is written to memory before invalidation. The source operand is a byte memory location."

Ironically, Intel have recently created a new "CLWB" instruction which causes a modified cache line to be written back to memory without flushing/invalidating it. I don't think any currently available CPU supports this instruction (or PCOMMIT) yet.

Owen wrote:Perhaps he meant clean, which empties the cache line.

There is no "clean" instruction on 80x86. I suspect you may be thinking of ARM or some other CPU that does everything different.

Brendan wrote:

Owen wrote:Regardless, they're an enormous waste of cache traffic - the processor will successfully do least-recently-used replacement anyway. If you are working on such large quantities of memory that the cache effects are important, and you can avoid reading or writing a location twice, just use a damn non-temporal read/write instruction.

For data that's only being read, CLFLUSH causes no additional RAM traffic as the cache line wasn't modified so no modified data has to be written back to RAM. It may or may not cause additional cache coherency traffic between CPUs, but (if only one CPU is using it) it's very likely the cache line will be in the "Exclusive" state (not the "Shared" state) and therefore no additional cache coherency traffic is needed either.

Brendan wrote: For non-temporal loads you're forced to use SSE (which would become a pain in the neck for "plain C" code that's reading bytes like my example); and when you're using multiple pieces of the cache line at different times the data/cache line may be flushed by the CPU before you're finished using it, which can waste RAM bandwidth (CPU re-fetching the same cache line from RAM multiple times because it doesn't know when if you're still using it or not).

Brendan wrote:

Owen wrote:Theres a reason why processor manufacturers don't tell you about the exact predictor setup of a processor and change it - it's because they, after all, want to be able to improve their processors from generation to generation. Or, even more importantly, they don't want to get locked into an inappropriate predictor design. Hell, consider, say, the Qualcomm Snapdragon 810 with 4x Cortex-A53 and 4x Cortex-A57. The Cortex-A53 is a little, in-order processor; the A57 is a big out-of-order machine. They have completely different designs, different performance characteristics, and different performance points.

Intel do tell you about the characteristics of their hardware pre-fetcher in their Optimization Reference Manual (and AMD do the same in their Optimisation Guide).

Brendan wrote: For all of the different ARM chips, I don't know. I assume you're right and that the average ARM manufacturer is a n00b that failed to provide adequate documentation.

Brendan wrote:Typically (for 80x86) the problem is that the programmer can't know which CPU the end user/s might be using, and therefore has to rely on generic assumptions.

Owen wrote:

Brendan wrote:

Owen wrote:Regardless, they're an enormous waste of cache traffic - the processor will successfully do least-recently-used replacement anyway. If you are working on such large quantities of memory that the cache effects are important, and you can avoid reading or writing a location twice, just use a damn non-temporal read/write instruction.

For data that's only being read, CLFLUSH causes no additional RAM traffic as the cache line wasn't modified so no modified data has to be written back to RAM. It may or may not cause additional cache coherency traffic between CPUs, but (if only one CPU is using it) it's very likely the cache line will be in the "Exclusive" state (not the "Shared" state) and therefore no additional cache coherency traffic is needed either.

CACHE traffic. Not RAM traffic. Your processor has limited capacity to issue memory operations. Those cache flush operations are almost certainly a waste of that capacity.

Owen wrote:

Brendan wrote:Intel do tell you about the characteristics of their hardware pre-fetcher in their Optimization Reference Manual (and AMD do the same in their Optimisation Guide).

Sure, but not the exact design.

Brendan wrote:They tell you what you need to know. They don't give you copious amounts of irrelevant information (e.g. a schematic diagram showing individual transistors).

Owen wrote:If you are working on such large quantities of memory that the cache effects are important, and you can avoid reading or writing a location twice, just use a damn non-temporal read/write instruction.

Owen wrote:they, after all, want to be able to improve their processors from generation to generation. Or, even more importantly, they don't want to get locked into an inappropriate predictor design.

Owen wrote:Hell, consider, say, the Qualcomm Snapdragon 810 with 4x Cortex-A53 and 4x Cortex-A57. The Cortex-A53 is a little, in-order processor; the A57 is a big out-of-order machine. They have completely different designs, different performance characteristics, and different performance points

Owen wrote:After all, no processor which sucked at running existing code ever succeeded without external influence...

embryo wrote:

Combuster wrote:

embryo wrote:range [ecx], [ecx+0xaaaa]; this range also will be used by following loop
...; some loop instructions

A cache miss will still prevent the first instruction of the loop from executing regardless of the preceding range statement, possibly out-of-ordering the next item in the loop and firing an automatic loading sequence. The absence of a cache miss will make the process slower due to decoding overhead.

You haven't got the idea. The idea was about declaring that some part of a code should be executed only when data is available.

Code: Select all

range [ecx] ; cycle 1, load [ecx]
mov eax, [ecx] ; cycle 2 - stalls for 98 more.
; cycle 100

vs

Code: Select all

mov eax, [ecx] ; cycle 1 - stalls for 99 more.
; cycle 100

range [ecx] ; cycle 1, load [ecx] - stalls for 99 more.
mov eax, [ecx] ; cycle 100 
; cycle 101

embryo wrote:If, for example, there is a server OS that being optimized for high performance calculations in a grid, then you still have an option to tune it up to the least common denominator. But if you tune it up to a particular hardware (with some schematics and etc) then the same performance would cost you tenth percents less. And in some special cases the cost can be improved more than twice. As a simple example you can look at SSE and AVX instructions and if you assume the least common denominator then your choice is with SSE, but if you tune a system up to AVX support then the performance raises twice as much as in the first case. Of course, detailed algorithms of the memory operations hardly would give us 100% performance increase, but in a cost competitive environment even 10% is a big gain.

Combuster wrote:You just turned your code into the following:

Code: Select all

range [ecx] ; cycle 1, load [ecx] - stalls for 99 more.
mov eax, [ecx] ; cycle 100 
; cycle 101

Which is actually worse.

long                         ;      enter long loop mode,
                             ;      may be this command can be omitted
                             ;      and it's job will be done by a first range instruction
range eax, ebx               ;      this range will be used by following loop
range [ecx], [ecx+0xaaaa]    ;      this range also will be used by the
                             ;      following loop
[set of loop instructions]   ;      some loop instructions (more than one instruction,
                             ;      but there should be some limit for the total number)

start                        ;      here processor and memory controller do their job
                             ;      of decoding loop instructions, starting prefetching
                             ;      process, executing some other code
                             ;      while data or the loop code are still not ready

Combuster wrote:Besides, in current x86 you can still prefetch or dummy-load [ecx] and then perform anything else you might be able to do

Combuster wrote:but more often than not you either do not know the range until very shortly before the actual loop or the data is already cached from an earlier access

Combuster wrote:Basically, hyperthreading is the better solution since you can actually do something completely unrelated with little extra thought instead of wasting overhead on microscheduling something where you have nothing to schedule anyway.

Combuster wrote:Your method already forces the use of more than one instruction pointer, so why not spend the additional silicon on something much more effective?

Brendan wrote:This is why I think software should be in an intermediate form and compiled to native when it's installed - so the compiler can optimise specifically for the actual CPU, rather than only being able to optimise for the lowest common denominator.

Brendan wrote:Of course if code was optimised specifically for a specific CPU, then you're probably going to want to disable the hardware prefetcher and use software prefetch instead. The hardware prefetcher has some nasty corner cases (e.g. accessing many small 128-byte arrays or structures, where the hardware prefetcher just makes things worse by over-fetching) and is mostly there for the benefit of "less optimised" code.

Brendan wrote:Also note that for most modern systems RAM bandwidth and some caches are shared by multiple CPUs. This means that something that improves performance for one process might also reduce performance for other processes and reduce the performance of the system as a whole.