Software Development Reference
Kip Landergren
(Updated: )
My cheat sheet for software development covering basic understanding, terminology, and workflows.
Contents#
- Hash Functions
- Booleans
- Numeral Systems
- Powers of 2
- Powers of 10
- Units
- Bit Shifting
- Encoding
- Permission Bits
-
Git Workflows
- Fork and Pull / Integration Manager / Integrator
- Centralized / Shared Repository
- Others
- Versioning
- Code Review
- Networking
- Data Structures
- Computational Complexity
- Algorithms
- FAQ
- Terminology
Hash Functions#
h: 2n → 2k
Generally:
- 2 k/2 operations before seeing collision, due to birthday paradox
Non-exhaustive list of desirable properties, depending on the application:
- avalanche effect - where output changes significantly relative to input
- randomness - can we predict output?
- uniformity - for every possible value are there the same number of inputs?
- one-way function - easy to compute, hard to invert
Applications:
- verification:
- file / data integrity
- password
- digital signature
- data identifier
Cryptographic Hash Functions#
SHA-1#
- fixed 160-bit (20 byte, 40 hex digits) message digest
- demonstrates good avalanche effect, where output changes significantly relative to input
- deprecated in 2017
$ echo -n 'hello world' | sha1sum
2aae6c35c94fcfb415dbe95f408b9ce91ee846ed -
$ echo -n 'hello world!' | sha1sum
430ce34d020724ed75a196dfc2ad67c77772d169 -
Booleans#
| 0 | false |
| 1 | true |
Beware! Unix command exit codes are:
| 0 | success |
| 1 | error |
Numeral Systems#
Positional Notation#
ijkradix ⇒ (i × radix2) + (j × radix1) + (k × radix0)
Binary - Base 2#
| bit | contraction of “binary digit” |
1012 ⇒ (1 × 22) + (0 × 21) + (1 × 20)
| 0000 | 0 |
| 1111 | 15 |
Octal - Base 8#
1018 ⇒ (1 × 82) + (0 × 81) + (1 × 80)
- 3-bit encoding
Hexadecimal - Base 16#
10116 ⇒ (1 × 162) + (0 × 161) + (1 × 160)
- 4-bit encoding
- capitalization is by convention; it does not matter
- considered “binary shorthand” because of the ease in exchanging 4 bits for 1 hex digit
- “hexa” is Greek for “six”, “decimal” is derived from Latin; the etymology is confusing
| Hex value | Decimal Value |
|---|---|
| 00 | 0 |
| FF | 255 |
Conversions#
| Decimal | Binary | Octal | Hexadecimal |
|---|---|---|---|
| 0 | 0000 | 0 | 0 |
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 2 |
| 3 | 0011 | 3 | 3 |
| 4 | 0100 | 4 | 4 |
| 5 | 0101 | 5 | 5 |
| 6 | 0110 | 6 | 6 |
| 7 | 0111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
Powers of 2#
| 20 | 1 |
| 21 | 2 |
| 22 | 4 |
| 23 | 8 |
| 24 | 16 |
| 25 | 32 |
| 26 | 64 |
| 27 | 128 |
| 28 | 256 |
| 29 | 512 |
| 210 | 1024 |
| 211 | 2048 |
| 212 | 4096 |
| 216 | 65,536 |
| 232 | 4,294,967,296 |
| 264 | 18,446,744,073,709,551,616 |
Powers of 10#
| 100 | 1 |
| 101 | 10 |
| 102 | 100 |
| 103 | 1000 |
| 104 | 10,000 |
| 105 | 100,000 |
| 106 | 1,000,000 |
| 107 | 10,000,000 |
| 108 | 100,000,000 |
| 109 | 1,000,000,000 |
| 1010 | 10,000,000,000 |
Units#
| byte | 8 bits (most common) |
| nibble | 4 bits; a play on words in that “a nibble is a portion of a bite (byte)” |
| word | the natural unit of data for a processor |
Why 8 bits to a byte?#
Convenience given that 8 is 23 and history with 7-bit ascii.
Bit Shifting#
For int-like types, left bit shifting by n multiplies the value by 2n (shown using Ruby):
10 << 1 # 10 * 2^1 = 20
10 << 2 # 10 * 2^2 = 40
10 << 3 # 10 * 2^3 = 80
10 << 4 # 10 * 2^4 = 160
Encoding#
ASCII#
- 7 bits wide, 8th can be used as parity bit
- American Standard Code for Information Interchange
Permission Bits#
| rwx | 7 | read, write, and execute |
| rw- | 6 | read and write |
| r-x | 5 | read and execute |
| r-- | 4 | read |
| -wx | 3 | write and execute |
| -w- | 2 | write |
| --x | 1 | execute |
| --- | 0 | no permissions |
| permission | octal | field |
|---|---|---|
| rwx------ | 0700 | user |
| ---rwx--- | 0070 | group |
| ------rwx | 0007 | other |
Selected common permissions:
| 0777 | rwxrwxrwx | everyone rwx |
| 0755 | rwxr-xr-x | owner rwx, everyone else r-x |
| 0655 | rw-r-xr-x | owner rw-, everyone else r-x |
| 0644 | rw-r--r-- | owner rw-, everyone else r-- |
Directory permissions have special meanings:
- read: user can read filenames
- write: user can [add,rename,delete] files if execute also set
- execute: user can enter directory and access files
This StackOverflow answer goes into more detail.
Git Workflows#
Fork and Pull / Integration Manager / Integrator
Contributors do not (necessarily) have commit access to a repository and instead fork it to create their own copy, work within that forked version, and communicate to the original repo’s maintainer (possibly through pull requests) that their forked repository’s branch has contributions ready for pulling and merging into the original repository.
Centralized / Shared Repository#
Multiple contributors have commit access to a repository and work on clones of it.
git-flow#
Useful for:
- aggregating multiple features into a single, testable, isolated release branch
- maintaining specific release versions
- unambiguous process steps
Consider alternatives if:
-
git rebase is preferred
-
a lightweight workflow is needed
-
Authoritative:
- A Successful git Branching Model by Vincent Driessen (nvie)
- nvie/gitflow GitHub repo with git extensions implementing the branching model
-
Perspectives:
- Why aren't you using git-flow? | Hacker News (2010 August)
- GitFlow considered harmful | Hacker News (2015 June)
- That "git-flow” (2016 February)
- What is wrong with “A successful Git branching model”? | Hacker News (2016 February)
- Please stop recommending Git Flow! | Hacker News (2020 March)
GitHub Flow#
Useful for:
- continuous deployment to production, like with a web app
- code review through GitHub’s Pull Requests
Consider alternatives if:
-
specific releases must be maintained
-
Authoritative:
-
Perspectives:
- Git email flow vs Github flow | Hacker News (2021 March)
Others#
- Git workflows - The Linux Kernel Archives
- GitLab Flow
- Comparing Workflows
- Git Feature Branch Workflow
- Trunk Based Development
- a simple git branching model (written in 2013)
- Patterns for Managing Source Code Branches
- Fossil vs Git | Hacker News
Versioning#
For Libraries#
Recognize:
- library versioning is about compatibility first, and new functionality second
- the main consumers are other software maintainers and package managers
Preferred versioning policy:
- use Semantic Versioning
- if you want to break backwards compatibility (e.g. increment the MAJOR version), create a new, differently named library instead
- avoid an automated determination and change of version; a human should be in the loop
Strive for:
- a publically declared versioning scheme
- a publically declared compatibility guarantee
- a unit test suite determining version compatibility
- a detailed CHANGELOG
For Applications#
Recognize:
- application versioning may have many varying consumers:
- end users
- the organization that creates and maintains the application, which itself may be split into:
- engineering interests
- product interests
- business interests
- marketing interests
- entities—which may be software themselves—that manage the application on behalf of the end users (e.g. an app store or an operating system)
Strive for:
- a context-appropriate scheme, like:
- MAJOR.MINOR, where MAJOR increment indicates a major product change and MINOR indicates a minor product change or bugfix
- Calendar Versioning, for when releases have a dependency or relationship to time
- channel-based releases, like ALPHA or BETA
- named releases
- target-based versioning, like for operating systems (e.g. macOS-10.15) or other software
Best Practices#
Recognize:
- Hyrum’s Law, which states: “With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.”
- the human consumer:
- comparing two integers for which is larger is straightforward
- “Spring 2021” means different things to a United States vs. an Australian audience
- some may view the next logical sequence member of 2.8, 2.9, ?? to be 3.0, not 2.10
Strive for:
- a versioning policy reflective of use and context
- making a human ultimately responsible for the version change decision; being informed by automated processes, like passing a test suite, is encouraged
- committing version metadata to source code
- automatically generating a build identifier using SCM software (e.g.
git describe --first-parentorgit describe --tags) for easy reference
Consider:
- The One Version Rule
- releasing beta or early access APIs so that libraries can support multiple versions
Schemes#
| Semantic Versioning (SemVer) | MAJOR.MINOR.PATCH, where MAJOR is breaking backward-compatibility, MINOR is additive, backwards-compatible changes, and PATCH is backwards-compatible bugfixes |
| Semantic Import Versioning | Go’s approach of encouraging libraries to follow SemVer with the added requirement that the import path must be file-local to its use and scoped to the major version |
| Calendar Versioning (CalVer) | versioning convention based on project release calendar; no hard and fast rules |
| Serial Versioning | each version is an increment of the previous |
Additional Resources#
- Spec-ulation Keynote - Rich Hickey
- The Principles of Versioning in Go
- CppCon 2017: Titus Winters “C++ as a "Live at Head" Language”
Code Review#
Gerrit#
Resources#
- Gerrit Code Review
- openstack/nova code review
- OpenDev Developer’s Guide using a gerrit-based development and review workflow
- Abandoning Gitflow and GitHub in favour of Gerrit | Hacker News (2016)
Networking#
OSI Model#
| Layer 7 | L7 | Application Layer |
| Layer 6 | L6 | Presentation Layer |
| Layer 5 | L5 | Session Layer |
| Layer 4 | L4 | Transport Layer |
| Layer 3 | L3 | Network Layer |
| Layer 2 | L2 | Data Link Layer |
| Layer 1 | L1 | Physical Layer |
Data Structures#
Array#
For dynamic (growable) arrays:
| access | O(1) |
| mutate (at beginning) | O(n) |
| mutate (at middle) | O(n) |
| mutate (at end) | O(1) |
Computational Complexity#
Algorithms#
Graph Traversal#
FAQ#
How to handle validating state?#
Scenario:
An object exists, and its state is valid. An object is modified, is its state valid?
The questions arise:
- should proposed state changes be validated in the modification method?
- if they are validated in the modification method, how could we really know if the object would have been invalid, were it given a chance to assume the new state?
- if they validated after modification, why is the object allowed to exist in an invalid state?
- how does the logic for what constitutes validity be used in all appropriate cases?
- how to handle atomic updates where multiple components of state may be modified at once? and if updated individually would constitute an invalid state?
This leads to an alternative path:
Create an immutable object which validates its state on construction, failing to create the object if invalid.
What does the “rc” suffix of files like .bashrc mean?#
The “rc” suffix stands for “run commands”.
Terminology#
- abstraction#
- 1.
The separation of the use from the implementation.
Related:
- angle brackets#
- 1.
< and >
Also: wakkas
Note: possibly called “wakkas” in reference to the sound Pac Man makes when eating the dots; used primarily in a programming context, especially Ruby.
Related:
- backtick#
- 1.
`
Also: grave accent
- blackbox testing#
- 1.
Testing the exported identifiers—the public API—without referring to unexported identifiers.
- braces#
- 1.
{ }
Also: curly braces, curly brackets, moustache brackets
Related:
- brackets#
- 1.
[ ]
Also: square brackets
Related:
- bug-for-bug compatibility#
- 1.
Preserving aberrant behavior in new implementations to not disrupt compatibility with consumers.
Related:
- build-time configuration#
- 1.
The settings for the software set during compile, bundling, or packaging.
Related:
- caret#
- 1.
The text cursor.
- 2.
^
Also: circumflex
- change-detector test#
- 1.
A test that is just a transformation of the code under test; results in testing implementation rather than behavior.
- compiler#
- 1.
- data abstraction#
- 1.
A methodology for structuring systems in such a way that much of a program can be specified independent of the choices involved in implementing the data objects that the program manipulates.
Related:
- declarative programming#
- 1.
Code style that expresses logic without specifying control flow.
Broader:
Related:
- dynamic programming language#
- 1.
A programming language that defers certain programming behaviors until runtime; not to be confused with a dynamically typed language.
Related:
- evergreen software#
- 1.
Constantly updated software, possibly without user control.
- feature flags#
- 1.
The use of configurable settings (flags) to selectively enable functionality (features)
Related:
- functional programming#
- 1.
Programs constructed by the application and composition of functions.
Broader:
- golden file#
- 1.
An immutable file representing the desired output of an operation; typically used to compare against while testing.
- imperative programming#
- 1.
Code style that expresses desired changes in program state.
Broader:
Related:
- inversion of control#
- 1.
- level#
- 1.
the severity / importance of the message. determines if message will be logged, where the message gets logged to, and when the logging system deletes the message, all which can be customized via configuration.
- paradigm#
- 1.
The classification of a programming language according to its features; e.g. “functional”
Narrower:
- parens#
- 1.
( )
Related:
- peek#
- 1.
Return value at location; could be by index (e.g. an array) or by operation (e.g. via
topon a stack) - performance analysis#
- 1.
the use of log lines and their timing data to provide insight into behavior
Related:
- race condition#
- 1.
- robustness#
- 1.
The likelihood that small changes in a specification will require correspondingly small changes in the program.
- runtime configuration#
- 1.
The settings for the executing software process read on startup.
Related:
- semantic linefeeds#
- 1.
technical writing / documentation technique of adding linefeeds after every sentence to make diffs easier to understand.
- side effects#
- 1.
- static programming language#
- 1.
A programming language that performs certain programming behaviors at compilation time.
Related:
- stream#
- 1.
A sequence of data objects.
- table tests#
- 1.
Aggregating test information—including input and expected output—into a data structure that is then passed to a test function that performs a test passing each unit of information.
Also: parameterized tests, data provider pattern
Note: “Table” is possibly a reference to table-driven programming or decision tables—an early technique where varying data is pulled out into lookup tables for one generic routine to then process unit by unit.
- telemetry#
- 1.
Timing data.
- telemetry#
- 1.
timing data
Related:
- transpiler#
- 1.
A source-to-source converter; a type of compiler.
Broader:
- upgrade cliff#
- 1.
The effort required to make use of a newer version of software (often a delta function; hench: “cliff”)
Related:
- volume#
- 1.