Super-simplified: Programming high performance code by considering cache

  • Code/data locality (compactness, % of each cache line that gets used)

  • Predictable access patterns: pre-fetch (instructions and data) friendly. This explains branching costs, why linear transversal might be faster than trees at smaller scales because of pointer chasing, why bubble sort is the fastest if the chunks fit in the cache.

  • Avoid false sharing: shared cache line unnecessarily with other threads/cores (due to how the data is packed) might have cache invalidating each other when anyone writes.

Loading

Super-simplified: What is a topology

‘Super-simplified’ is my series of brief notes that summarizes what I have learned so I can pick it up at no time. That means summarizing an hour of lecture into a few takeaway points.

These lectures complemented my gap in understanding open sets in undergrad real analysis, which I understood it under the narrow world-view of the real line.


X: Universal set

Topology ≡ open + \left\{\varnothing, X\right\}

Open ≡ preserved under unions, and finite intersections.

Why finite needed for intersections only? Infinite intersections can squeeze open edge points to limit points, e.g. \bigcap^{\infty}_{n}(-\frac{1}{n},\frac{1}{n}) = \left\{0\right\}.

Never forget that \left\{\varnothing, X\right\} is always there because it might not have properties that the meat open set B doesn’t have. e.g. a discrete topology of \mathbb{Q} on (0,1) = B \subseteq universal set X=\mathbb{R} means for any irrational point, \mathbb{R} is the only open-neighborhood (despite it looks far away) because they cannot be ‘synthesized*’ from \mathbb{Q} using operation that preserves openness.

* ‘synthesized’ in here means constructed from union and/or finite intersections.


[Bonus] What I learned from real line topology in real analysis 101:

  1. Normal intuitive cases
  2. Null and universal set are clopen
  3. Look into rationals (countably infinite) and irrationals (uncountable)
  4. Blame Cantor (sets)!

 

 

Loading