notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

PerformanceAwareProgramming.md (5265B)


      1 # Performance-Aware Programming
      2 
      3 **Source:** [https://www.computerenhance.com/p/table-of-contents](https://www.computerenhance.com/p/table-of-contents)
      4 
      5 ## Links
      6 
      7 - SIMD
      8     - SSE - 4
      9         - streaming simd extensions
     10     - PADDD
     11         - Pack (wide) add
     12             - takes in 4 inputs and outputs
     13         - just 4 adds, but only have to take in one instruction 
     14             - each of the inputs are aligned as before
     15     - AVX - 8
     16     - AXV512 - 16
     17 - IPC/ILP
     18 - x64
     19 - [8086](8086.md)
     20 - [RISC](RISC.md)
     21 - LoopUnrolling
     22 - VectorComputing
     23 - Register file
     24 - L1,L2,L3 (dedicated,dedictated,shared)
     25     - times (cycles): 3-4, 14, 80
     26     -  sizes: 64kb, 256kb,  8mb
     27 - MainMemory
     28     - 250 cycles
     29 - Haversine distance
     30     - dist on surface of sphere
     31 - [Mov](Mov.md)
     32 - FunctionLabels
     33     - function labels are just syntatic sugar that gets converted to a goto in the binary.
     34         - mind blown
     35 - [Jump Table](JumpTable.md)
     36 - SingleTranslationUnitBuild
     37 - StackPointer (SP)
     38     - Points to the top of the stack
     39 - BasePointer (BP)
     40     - Points to the base of the current stack frame
     41         - often this is used along with an offset to maintain a consistent
     42             - reference to values on the stack (given that it doesn't move
     43                 - except when pushing more frames)
     44     - Base pointers may be removed for optimization (to use that register for other stuff), which is called frame pointer optimization
     45         - disable this in gcc with -fomit-frame-pointer
     46             - frame pointer is the base pointer
     47 - [Instruction Pointer](InstructionPointer.md)
     48 - Flags Register
     49     - Register that tracks information about execution, like the output of a cmp / sub, including things like zero, negative, and things like that. 
     50 - cmp / sub relation -- cmp is just sub without updating the destination because they both set flags the same way (in 8086)
     51 - Segmented Addressing
     52     - Not common anymore, but is used when there are more addresses than the word size can accommodate.
     53 - Loop
     54     - Instruction that's a decrement and then jnz
     55         - This is generally not used because it's often slower than dec / jnz
     56             - One diff is the loop instruction doesn't set flags
     57 - shr
     58     - shift right
     59     - logical / bitwise shift
     60 - sar
     61     - arithmetic shift right
     62     - maintains signedness
     63         - shifts everything right except the leftmost bit (signed bit)
     64 - shl
     65     - shift left
     66 - sal
     67     - arithmetic shift left 
     68     - this is the same as shl due to two's complement
     69 - test
     70     - is equivalent to and, but doesn't write back
     71     - similar to how cmp is sub without writing
     72 - lea
     73     - load effective address
     74     - calculates effective address and writes it to a register
     75         - can be more efficient if the effective address is reused
     76 - inc, dec
     77     - increment, decrement
     78 - push / pop
     79     - push and pop from the [Stack](Stack.md)
     80 - instruction performance characteristics
     81 - 8086 vs x86_64
     82     - 8086 register addressing is a subset of x86_64
     83     - to extend registers to 32 bits, we use e{register} such as eax to say the extended ax register
     84     - registers are now 64 bits though so we also have r{register} like rax
     85     - additional 8 registers called:
     86         - R8,R9,R10,...,R15
     87             - these are addressable in their lonesome or with B, W, and D.
     88                 - e.g. R15D -- first 32 bits
     89     - We aren't constrained to the lookup table for effective address calcuation, instead we can use any register additions + disp
     90         - We can also multiply the second register value by 1, 2, 4, or 8
     91             - e.g. [eax + esi*8]
     92 
     93 ---
     94 
     95 - Haversine distance
     96 - json parsing
     97     - general recommendations about how to do things often result in un-necessary complexity and performance degradations
     98     - json parsers can be relatively complex and slow relative to a binary approach
     99         - it's overcomplicated in part because it's too general purpose
    100 - rdtsc
    101     - read timestamp counter
    102         - this gives us a 64-bit value (half in two different registers) which is how much time the processor believes has elapsed since it started
    103             - this just counts up, and ppl can touch it and it'll just count from there
    104         - if >64-bits, it'll wrap around
    105         - every cycle causes an increment
    106             - this is based on the crystal that modulates clock speed
    107     - main reasons why this isn't perfect
    108         - rdtsc may take some time itself
    109         - the value can be changed
    110         - since its inception, multi-core systems have become more popular
    111             - each core may have a different frequency and for some reason rdtsc started measuring invariant tsc, which is where the tsc is consistent across all cores (even if boosting / sleeping).
    112             - so basically, rdtsc is now some sort of ~ analog for clocks, but not actually
    113                 - this allows cross core timing, which is nice, but that's the extent of the goodness as the tsc now isn't for counting cycles
    114                 - invariant tsc is probably base clock, not necessarily our core
    115                 - so it's just a precise wall clock now
    116     - added in 586 (before x86_64, after 8086)
    117     - while rdtsc is annoying, it is basically always there, whereas alternatives may not be
    118 - rdtscp
    119     - nice out of order execution properties