Fact Sheet for computer science

In this blog I will include all the facts about algorithms or data structures.

Insertion Sort vs Merge Sort
Which sort to use and when is important or must know practical limitations. It is not necessary to blindly implement the best algorithm always.
Normally in languages like Java or Python sort is implemented as Insertion Sort or Quick Sort as default system sort.
Merget Sort - O(n lg n) - when input is more than 2^12
Insertion Sort - O(n^2) - when input is less than 2^12

Binary Tree fanout :
Height of binary tree is calculated as
h <= lg{f} n , where f= fanouts possible at each level for each node. To redue disk reads fanout can be increased or can be adjusted at runtime depending upon number of nodes. Normally 1000 fanouts can contain 1 million nodes in the tree which is quite sufficient.

Use C wrapper for computation:
C is fast. But when. Why everyone is not using C then?
There are issues with C wrt memory management, reading files, DB connections, finding developers, learning curve, fast development (RAD). But still I agree that for computations C is the best. C can give 20X improvement when load is computations. In case when it is required to compute keys very fast (as in large systems, to calculate key for DHT) C wrapper can improve performance depending upon the load curve.

===============================================================================

Registers & CPU cache (1 nanosecond): These are small, expensive and very fast memory slots. Memory controllers try mightily to keep this space populated with the data the CPU needs. A cache miss means a 100X speed penalty. Even with a 95% hit rate, CPU cache misses waste half the time.

Main memory (10^2 nanoseconds): If your computer was an office, RAM would be the desk scattered with manuals and scraps of paper. The kernel is there, reserving Papal land-grant-sized chunks of memory for its own mysterious purposes. So are the programs that are either running or waiting to run, network packets you are receiving, data the kernel thinks it's going to need, and (if you want your program to run fast) your working set. RAM is hundreds of times slower than a register but still orders of magnitude faster than anything else. That's why server people go to such lengths to jam more and more RAM in.

Solid-state drive (10^5 nanoseconds): SSDs can greatly improve the performance of systems with working sets too large to fit into main memory. Being "only" one thousand times slower than RAM, solid-state devices can be used as ersatz memory. It will take a few more years for SSDs to replace magnetic disks. And then we'll have to rewrite software tuned for the RAM / magnetic gap and not for the new reality.

Magnetic disk (10^7 nanoseconds): Magnetic storage can handle large, contiguous streams of data very well. Random disk access is what kills performance. The latency gap between RAM and magnetic disks is so great that it's hard to overstate its importance. It's like the difference between having a dollar in your wallet and having your mom send you a dollar in the mail. The other important fact is that access time varies wildly. You can get at any part of RAM or SSD in about the same time, but a hard disk has a physical metal arm that swings around to reach the right part of the magnetic platter.

Network (10^6 to 10^9 nanoseconds): Other computers. Unless you control that computer too, and it's less than a hundred feet away, network calls should be a last resort.