
## JavaScript Modularity

For the longest time, JavaScript was purely a language of the web. In the days of jQuery (and before), it was common to include all of the JavaScript that a website needed in a single file. This meant that we would define objects like variables and functions in the global scope, which had the benefit of being able to access everything necessary in that file. While using the default global scope for everything is convenient, it can be error-prone and difficult to maintain. When code begins to grow in size and complexity, developers often reach for modularity. For the longest time, JavaScript in the browser didn't have a great solution for modularity. You could separate code in different script files, but there was no guarantee that objects wouldn't be mutated in the global scope.

As the web development domain continued to evolve to more Node-based tooling, the need for modularity became more apparent. In 2018 ECMAScript Modules were made officially available in all major browsers. This meant that JavaScript code could be defined, exported, and imported in modules that run directly in the browser. Over time Node.js began to support ES Modules, while also supporting an existing module solution called CommonJS. ES Modules and CommonJS share a common goal of modularity in JavaScript, but unfortunately, they don't play too nicely when being used in the same project. I recently was working on a project that used ES Modules in the browser. I wanted to use Jest to write some tests for these modules and I ended up having to use an experimental Node.js flag to run the tests with ES Modules. My goal for this post is to simply understand more about each of the module systems, which I believe will help me in the future when working in frontend or Node-based codebases.

## CommonJS

According to the Node.js documentation, CommonJS is the original packaging solution for JavaScript. CommonJS isn't available to use in browsers so it is used in purely Node-based server-side applications. If you're wondering why CommonJS modules can be used within popular libraries like React, it's because that code is often transpiled and bundled before sending to the browser. If you're not too familiar with CommonJS, but have imported modules in JavaScript using the `require()` method then you've used CommonJS. The method of referencing other modules with `require` is the main difference between CommonJS and ES Modules.

Node.js will default to CommonJS unless otherwise specified by file type or an indication in the `package.json`, but it is best to be explicit when defining module type since Node.js supports CommonJS and ES Modules. There are a few ways to specify that modules are using CommonJS in a Node application.

- Use the file extension `.cjs`
- Set the `"type"` field to `"commonjs"` in the `package.json`
- Including `--input-type=commonjs` when invoking Node from the command-line

Another aspect of CommonJS that differs from ES Modules is the method of exporting members. Node wraps the module in a function wrapper which can be used to access some global-like objects. For example, the module wrapper provides a `module` object that the module author can use to export members from a module by setting the `exports` property. The module wrapping occurs before any module code is executed.

```javascript
(function (exports, require, module, __filename, __dirname) {
  // Module code actually lives in here
});
```

Let's put these CommonJS pieces together with an example. We'll define a module called `ai.js` which exports a function called `processPrompt`. The `ai` module is then required and referenced in another module called `prompt.js`.

```javascript
// ai.js

const processPrompt = (prompt) => {
  switch (prompt) {
    case "Are you human?":
      return "No, I'm your friendly neighborhood AI.";
    case "Will you take my software engineering job?":
      return "Yes, but not today.";
    default:
      return "I'm sorry, you've reached your request limit.";
  }
};

module.exports = {
  processPrompt,
};
```

```javascript
// prompt.js

const { processPrompt } = require("./ai");

console.log(processPrompt("Are you human?"));
console.log(processPrompt("Will you take my software engineering job?"));
console.log(processPrompt("Why does time only flow in one direction?"));
```

By running `node prompt.js` we'll see this output.

```shell
$ node prompt.js
No, I'm your friendly neighborhood AI.
Yes, but not today.
I'm sorry, you've reached your request limit.
```

CommonJS seems to be the de-facto method of modularizing JavaScipt that is meant to run on the server. In my opinion, things got a little more complicated when Node decided to support ES Modules.

## ES Modules

Modularity isn't anything new to the Node.js ecosystem, but it is something relatively new to the JavaScript that we run in browsers. It wasn't until mid-2018 that all major browsers shipped with the ability to natively import and export from modules in JavaScript, which was accomplished through ES Modules. The implementation details behind CommonJS and ES Modules are presumably quite different, but they both have the same goal of providing modules in JavaScript. Two keywords make ES Modules visibly different from CommonJS. They are `import` and `export`, pretty simple in my opinion.

To use ES Modules natively in the browser we can simply add `type="module"` to the `<script>` tag that is referencing the module.

```html
<script src="main.js" type="module">
```

Since the introduction of ES Modules to the web, Node.js has also adopted support for them. In Node.js we have a few options to tell the JavaScript engine ES Modules should be used for files. The options are quite similar to those used for CommonJS, but slightly different to indicate ES Modules.

- Use the file extension `.mjs`
- Set the `"type"` field to `"module"` in the `package.json`
- Including `--input-type=module` when invoking Node from the command-line

Files with the extension of `.mjs` can also be used when referencing modules in code targeting the browser.

As I mentioned the `import` and `export` keywords are the main user-facing differentiation between ES Modules and CommonJS. The `import` keyword is used to import objects or functions from another module or file. The `export` keyword is used to expose module members (objects and functions) that can then be imported by other modules.

> The import and export keywords are to ES Modules what the require function and module.exports object is to CommonJS respectively.

That declaration may be slightly reductive, but that's how I view them. Obviously, the way that the modules are parsed and evaluated by the respective JavaScript engines is bound to be quite different. Luckily as developers, we don't have to worry about their low-level implementation _too often_.

If we were to translate our previous code sample to ES Modules, there are only a few lines that need to change. In `prompt.js` we need to change the `require` method to the `import` keyword.

```javascript
// prompt.js
import { processPrompt } from "./ai";
// rest of code
```

Similarly in the `ai.js` we need to change `module.exports` to `export`.

```javascript
// ai.js
// rest of code
export { processPrompt };
```

In this post, we looked at CommonJS and ES Modules through the lens of the need for modularity and the environments they are used in. There is a ton of great documentation available to learn more about both of these module systems. So if you're interested in learning more I suggest using this post as a foundation to go deeper in those areas.


I was recently working on a project involving quite a bit of JavaScript. I always knew about ES Modules and CommonJS, but I never knew much about their differences. This post is a result of my exploration of CommonJS and ES Modules to learn more about their history and use cases.

Exploring CommonJS and ES Modules


When it comes to comprehensive command-line tools, FFmpeg definitely ranks among the top in terms of popularity and usage. FFmpeg was released in 2000 and has since become a household name in the video and audio processing industry. If you've had any experience with FFmpeg, you'll most likely know that as a tool it is both broad and deep. The breadth of functionality ranging from video to audio along with the depth of being able to decode, encode, transcode, mux, demux, stream, and filter media makes it a powerful, but also a daunting tool. The good thing for users is that the documentation is comprehensive and complete, although due to the sheer magnitude of functionality, it may be difficult for newcomers to digest. That's why I'd like to take a step back and break down this complex tool into some core fundamentals that provide a platform for learning more in the future. Let's start with the command specification.

## The FFmpeg Command

If you've worked with command-line applications before then the FFmpeg command structure may not be too surprising. With that being said FFmpeg comes with a long list of possible options and flags that can be quite challenging to understand. For this reason, I think it's best to start with the general structure of an FFmpeg command.

```shell
ffmpeg [global_options] {[input_file_options] -i input_url} ... {[output_file_options] output_url} ...
```

The first piece of the command `ffmpeg` is the entry point to the FFmpeg executable. Unless you've modified the name of the executable or have configured an alias to call it, invoking the FFmpeg executable will be consistent no matter where you're running the command. In its simplest form, FFmpeg is a program that accepts one or more inputs, processes those inputs, and produces one or more outputs. I found the FFmpeg "API" to be quite composable once I was able to grasp the high-level command structure.

### Global Options

The next group of options to cover is the **optional** `global_options`. The global options are meant to be applied to the command as a whole, rather than targeting specific streams or input/output files. For this reason, global options can only be included in a command once. The global options should be the first set of options included in the command before defining any input/output files and options. I won't define a comprehensive list of all the global command options available, but I think a great example of a global option is `-y`, which indicates that output files should automatically overwrite existing files if they exist.

If you'd like to see more examples of global command options head over to the [documentation](https://ffmpeg.org/ffmpeg-all.html) and search for "(global)". The search results should include most global options as they are denoted with "(global)" in their definitions. Now we'll move on to the input file and its options.

### Input Options

As I mentioned before, FFmpeg accepts **one or more** input files as part of a command. The input file is denoted with the `-i` flag. It is best to include all input files immediately after global options before any output options or files are included.

```shell
ffmpeg -i input.mp4 -r 30 output.mp4
```

When dealing with input (and output for this matter) options order is important because by default the options will be applied to the next file in the command. For example, the command below accepts two input files. The `-ss` option seeks to the specified position in the input file, which is included twice in the example to seek to different times in each input file. The command itself will result in two gifs being created with the specified length of 5 seconds (`-to 5`) a framerate of 10 fps (`-r 10`) and resized output (`-vf scale=200:-1`).

```shell
ffmpeg -ss 00:00:05 -i input1.mp4 -ss 00:00:01 -i input2.mp4 

# The rest of the command is related to the output
-to 5 -r 10 -vf scale=200:-1 -map 0 output1.gif -to 5 -r 10 -vf scale=200:-1 -map 1 output2.gif
```

Input options are a little less common than output options because typically the goal is to process the unmodified input, but understanding how to set up input files and options will be helpful for the next topic of output files and their options.

### Output Options

The output file URL and its options are structured similarly to their input counterparts with the difference being that they affect the result of the command instead of the input. It is important to remember that order matters with respect to options as they relate to multiple files. Options will only apply to the next file that is listed in the command.

If we continue to look at our example from the input commands, we'll notice that we have to specify the output options twice, once for each output file. Command options can be used twice in the same command as long as they are not used twice on the same file. We also include the `-map` option using the zero-based index of the input files to select which input the output options should be applied to.

```shell
ffmpeg -ss 00:00:05 -i soccer.mp4 -ss 00:00:01 -i soccer.mp4 

# Output options for the first output file (and first input file)
-to 5 -r 10 -vf scale=200:-1 -map 0 output1.gif 

# Output options for the second output file (and second input file)
-to 5 -r 10 -vf scale=200:-1 -map 1 output2.gif
```

Many output options are quite specific to the task at hand. For example, transcoding to fmp4 will require a set of output options completely different than transcoding to DASH. For that reason, I want to avoid going into too much detail about specific options. If you are needing information about a certain task I highly recommend checking out the official documentation.

## FFmpeg Command Workflow

So far this post has mostly been about the format and structure of FFmpeg commands. Before wrapping up I did want to touch on the general transcoding pipeline that FFmpeg uses. I'll be upfront in saying that this isn't anything unique or hard to find as there are quite useful diagrams in the FFmpeg documentation. With that being said I'd like to touch on the phases of the pipeline and give a little bit of context on what each is responsible for.

1. Demux the input into encoded data packets
1. The decoder decodes each packet into frames
1. The encode encodes each frame into the encoded data packets
1. Mux the encoded data packets into the necessary format specified by the output file

Each stage of the pipeline has a responsibility in the transcoding process.

1. Demultiplex (demux)
    - Responsible for separating the input file(s) into packets
2. Decode
    - Converts the demuxed packets into the raw media (video, audio, subtitles) format
3. Encode
    - Convert the raw media that was decoded into the format required by the output format
4. Multiplex (mux)
    - Package up all of the encoded packets into the necessary output file(s)

While this is a simplistic and reduced example, I think it covers the general process pretty well. There are obviously more complex workflows that involve filter graphs or other operations, but those are much more nuanced and specific to the type of work being done.

In this post, we've covered the FFmpeg command structure and general processing workflow. With all of this information in hand, you should be ready to take on more complex scenarios with confidence.


FFmpeg can do just about anything with video and audio processing as long as you know what to ask. In this post, I will break down the different aspects of an FFmpeg command to better understand how FFmpeg processes them.

The Anatomy of an FFmpeg Command


## Running FFmpeg in the Browser

I recently started a little project that involves running FFmpeg directly in the browser using [ffmpeg.wasm](https://ffmpegwasm.netlify.app/). The project is still **very** early and I'm not totally sure where I'm going to take it or if I'll continue working on it long-term. For now, I'm having fun learning about WebAssembly, while also expanding my knowledge of FFmpeg. At the time of writing the [site](https://ffplayground.netlify.app/) simply allows you to select a video file to "upload", which then results in an FFmpeg command running to generate a JPEG from a frame of the video. Nothing too exciting, but I've had some thoughts about potentially creating an FFmpeg command builder or providing autocompletion for FFmpeg commands. This could allow for quick feedback while iterating on creating FFmpeg commands. If any of this sounds interesting, head over to the [repo](https://github.com/aaronmbos/browser-ffmpeg) on GitHub and give it a star.

If you've got to this point in the post and don't really know much about FFmpeg, that's totally cool. I have a particular interest in it given that I work on software every day that relies on it. With that being said this post is more focused on the potential of WebAssembly in the browser rather than discussing the details of FFmpeg.

## FFmpeg.wasm

As a quick example of what is possible with WebAssembly I want to go into a little bit of detail about the [ffmpeg.wasm project](https://github.com/ffmpegwasm/ffmpeg.wasm) itself. FFmpeg is a C program that is used for just about anything you can imagine in the world of video and audio processing. As you may know, C code does not run natively in the browser, so how does ffmpeg.wasm work? The answer is WebAssembly. I'll dive into some of the details in the next section but at a high-level ffmpeg.wasm works by transpiling the original C code into WebAssembly. Since WebAssembly can run in the browser, it brings the media processing powers of FFmpeg to the web.

A few other popular examples of WebAssembly being used on the web are [Figma](https://www.figma.com/blog/webassembly-cut-figmas-load-time-by-3x/), [Adobe Acrobat on the Web](https://blog.developer.adobe.com/acrobat-on-the-web-powered-by-webassembly-782385e4947e), and .NET's client framework [Blazor](https://dotnet.microsoft.com/en-us/apps/aspnet/web-apps/blazor). I'm sure there are hundreds of other great examples out there as well. WebAssembly is not necessarily "new", but it is growing in popularity. In the next section, we'll look at a few features that make WebAssembly such an appealing tool for building with performance in mind on the web.

## WebAssembly

I've touched on some examples of WebAssembly in the wild, but I haven't gone into what makes it "special". WebAssembly, commonly referred to as "Wasm", is not a programming language that you'll find many (if any) people writing by hand. The best way to describe Wasm is a "compilation target". I like to think of WebAssembly as the result of compiling code from another language like C, Rust, Go, C#, etc. The main goal of Wasm is to enable high-performance applications on the Web. In my opinion, there are three key features of Wasm that contribute to the overall goal of "high-performance web applications".

1. Fast
1. Safe
1. Portable

### Key Feature: Speed

Wasm is able to achieve near-native performance in the browser by taking advantage of common hardware capabilities. Another factor in the speed of Wasm is that the code itself is a low-level, efficient binary format that is quicker for browsers to load and execute. While I wasn't able to find any "official" benchmarks comparing Wasm to JS, it seems that Wasm _typically_ runs 1-3 times faster than JS in the browser. This may not seem like a lot, but in applications where performance matters, that difference can make or break the user experience of the application.

### Key Feature: Security

Speed is great, but another very important feature of Wasm is security. I would argue that in most cases speed is irrelevant if the execution environment isn't safe for users or developers. For that reason, Wasm executes in a memory-safe, sandboxed environment, which claims to prevent data corruption and security breaches. Wasm provides no access to the environment that the code is executed on. Wasm is able to access system resources and perform IO when it is allowed by the embedder (the embedder defines the environment that Wasm will be hosted in).

### Key Feature: Portability

While this post and most of the focus on WebAssembly is scoped to running it on the web, one of the key features of the Wasm code format is that it is platform agnostic. Wasm's architecture does its best not to make assumptions about the underlying hardware that it is run on. This means that Wasm is built to take advantage of both common and modern hardware components. Wasm has started to become more common on the web, but it is possible to run it outside of the web given its platform-agnostic architecture. An example of WebAssembly outside of the browser is "WASI" or [The WebAssembly System Interface](https://wasi.dev/), the goals of WASI appear to align well with Wasm in general, but seem to be more targeted at portability and security.

I think that overall Wasm's speed, security, and portability make it an attractive tool for enabling high-performance code on the web. This post is by no means meant to be a deep dive into everything that Wasm has to offer, but rather an introduction to a technology that operates at a different level than what most developers are used to dealing with. There is a lot of great information available for WebAssembly and if you're interested in learning more I think the [specification](https://webassembly.github.io/spec/core/index.html) is a great place to start. It provides some high-level information along with everything you'd expect from a formal specification.


The introduction of WebAssembly (Wasm) has enabled developers to create experiences on the web that rival native performance. In this post, I'll provide an introduction to WebAssembly and also share an example of how it is leveraged to run FFmpeg directly in the browser.

Running FFmpeg in the Browser with Wasm


## What are conventional comments?

Code review is an integral part of working on software collaboratively. The collaboration may be at work with team members, on an open source project with other contributors, or on a school project with classmates. Regardless of the situation, code review is almost guaranteed to be required before merging changes.

Code review is also time consuming. The back and forth communication on initial and follow-up changes can go on for hours, days, and even weeks before the final approval is given for a set of changes. With that being said, wouldn't it make sense to look for ways to make code reviews as simple as possible? I think so.

This is where conventional comments come in. At their core, **conventional comments** (not to be confused with [conventional commits](https://www.conventionalcommits.org/en/v1.0.0/)) are code review comments that follow a predefined set of standards. We'll go into some examples of standards later in this post, but ultimately the standards can be as rigid or flexible as needed to fit the needs of the team.

## Structure of conventional comments

As I mentioned previously, there isn't a globally defined standard for structuring conventional comments, but I think this [site](https://conventionalcomments.org/) provides a great starting point. In my experience, I haven't needed to deviate too much from the comment structure defined on the referenced site.

```
<label> [decorations]: <subject>
[discussion]
```

The `label` and `subject` are required fields (surrounded by `<>`), whereas the `decorations` and `discussion` fields are optional (surrounded by `[]`). Following this comment format provides a platform for **description, but not distracting** context for each comment. The conventional comment site provides a lot of great examples as well as a list of great labels and decorations to get started. In my day to day I've used the following labels most commonly.

- suggestion: propose an improvement or change (could be blocking or non-blocking)
- nitpick: trivial request based on preference
- question: ask submitter for clarification or relevance
- thought: useful for providing helpful context and sparking discussion

While this list it thorough, it is not exhaustive. The great thing about this format is that it can be adapted to fit the requirements of any team that applies it.

## Why are conventional comments helpful?

If you've never experienced bad code reviews or never considered ways to improve the code review process, you may be wondering why conventional comments are beneficial? In my opinion conventional comments benefit both the submitter of the code review and also the individual reviewing the code.

From the **reviewer** side of the coin conventional comments allow for clear expression of intention and tone in each comment. This reduces the chance for friction or confusion that could result from an unclear or ill-thought-out comment. In this same vein I think conventional comments force commenters to put a litte extra thought and care into the comments that are left, which leads to higher quality reviews.

Since conventional comments reduce confusion and friction, this results in a quicker code review process with potentially less back and forth. The submitter should understand the action that needs to happen when responding to a conventional comment. For example, the change requested in this comment needs to be addressed before approval.

> suggestion (blocking): Let's move this guard clause earlier to exit sooner in the case of failure.

From the perspective of the code review **submitter**, the fact that the the "gray area" is removed with the use of conventional comments is key. There shouldn't be any ambiguity as to what should happen as the result of a comment.

The final benefit of using a conventional comment format is parasability. We can easily request and parse PR comments to understand what kind of review is taking place. Are we most leaving "nitpick" comments? Maybe we need to adjust the linter or format tool settings to catch some of these issues during development. Are there a lot of "issue" comments? Maybe engineers need to be more better about understanding requirements before and throughout development.

These are all reasons why conventional comments can benefit code reviews for any team, even if the team doesn't think code review is an immediate concern.

Analyzing PR comments with GitHub API

To demonstrate the value behind the parsability aspect of conventional comments I'd like to share a simple example using the GitHub API to request PR comments on a repo. This example is pretty basic, but I think it shows the potential for understanding the nature of comments being submitted by reviewers in a repo.

I can think of a use case where a report is generated to understand the number of nitpicks, suggestions, issues, etc have been made on PRs for a given repo over a period of time. This can all be done easily with a standardized format.

The script below is written in Ruby and is pretty straightforward. It does require a valid token for GitHub authorization which I've omitted from the example.

1. Make a request to the GitHub API
2. Parse the response as JSON
3. Print the necessary to the console

```ruby
require 'net/http'
require 'json'

uri = URI('https://api.github.com/repos/aaronmbos/nextjs-blog/pulls/comments')

req = Net::HTTP::Get.new(uri)
req['Accept'] = 'application/vnd.github+json'
req['Authorization'] = "Bearer #{gh_token}"
req['X-GitHub-Api-Version'] = '2022-11-28'

res = Net::HTTP.start(uri.hostname, uri.port, use_ssl: true) do |http|
  http.request(req)
end

JSON.parse(res.body).each { |comment| puts "#{comment['body']} by @#{comment['user']['login']}" }
```

The particular repo that I am querying only has a single PR [here](https://github.com/aaronmbos/nextjs-blog/pull/1). As you can see the output from the script reflects the current comments that have been made on the PR.

![conventional-comment-script](https://res.cloudinary.com/aaron-bos/image/upload/v1675131516/conventional-comment-script_qrkq66.png)

In this post, I've provided an opinionated overview of what I believe to be the value of conventional comments for teams. There's no one-size-fits-all solution and I hope that you are able to take some of these opinions and apply them to improve your team's code reviews!


In this post, I'll present my case for using conventional comments in code reviews. I've been an advocate of conventional comments for about a year and have enjoyed using them. I'm hoping to share the benefits so others can adopt their own standards for code review. Let's dive in!

My Case for Conventional Comments


Collections are an integral part of almost any application that we build or maintain as software engineers. The concept of traversing collections with a for-loop is often one of the first paradigms learned by new engineers. Collection-like objects exist in most, if not all, languages. In C# we have several options when it comes to collections and each option comes with tradeoffs. As software engineers, it is our job to choose the right tool for the job. The decision of what kind of collection to use for a given scenario needs to consider the context in which the collection will be used. We should ask ourselves _Will the collection be iterated, searched, or manipulated heavily in the most common use cases?_ The collection type we choose for a given scenario could have massive performance impacts on the application and its users.

We will focus on a few collection types in C# to determine how they perform in regard to [Big O notation](https://en.wikipedia.org/wiki/Big_O_notation) when searching for and manipulating elements of each collection type. This post doesn't require you to be an expert in Big O notation, but it does assume a basic understanding of the topic. I will be focusing on the following collection types.

- `List<T>`
- `Dictionary<TKey, TValue>` & `HashSet<T>`
- Sorted collections

There are many other collection types that could be covered, but I wanted to focus on the types that I've used and seen most in my career. If you're interested in learning more about the Big O notation in regard to other .NET collection types, I would highly encourage digging into it for yourself!

## `List<T>`

I would consider `List<T>` to be the most commonly used collection type in the .NET ecosystem. That means we should understand how we can use it effectively and its performance when carrying out certain tasks. In terms of Big O notation, I'd say that most `List<T>` operations can be expected to be linear or **O(n)**. A linear algorithm's runtime is directly affected by the size of the input being processed. As the input size grows the runtime should grow linearly proportional to the input growth.

### Manipulating lists

Manipulating a collection is a common operation and typically involves adding or removing items from the collection. Normally the add and remove functionality is a linear operation. Below is a screenshot of benchmark results adding a random number to a `List<T>` at increasing sizes. As the size of the list grows, the mean runtime also grows _nearly linearly_.

![list-add-linear](https://res.cloudinary.com/aaron-bos/image/upload/v1673574244/list-add-linear_a5kyly.png)

While typically list manipulation runtimes are linear, there is an exception when adding to lists. When a list is created, there is an overloaded constructor that accepts an integer to indicate the `Capacity` of the list. If we create a list with a defined capacity and the `Count` property at the time of adding is **less than** the `Capacity`, then adding to a list is **O(1)** or constant time. The reason for this is that the underlying array does not need to be expanded to accommodate the new element. This means that the speed of the operation is not affected by the size of the input (in this case the size of the collection). We can see this in action in the benchmarks below. As the input size grows linearly, the runtime of adding an element to the list remains constant.

![capacity-list-add-constant](https://res.cloudinary.com/aaron-bos/image/upload/v1673574477/capacity-list-add-constant_h7wsya.png)

### Searching lists

When working with collections we often need to search the collection for a particular element. This could be with `.Find`, `.Contains`, `.IndexOf`, `.Where`, and other methods that look for a particular element in a collection. For this reason, it's important to understand that the runtime of searching for an element in a list is also O(n) or linear. The algorithm to find an element most likely needs to iterate through each element to find the one that it is looking for. In the worst-case scenario, the item isn't in the list and we've had to look at every element. We can see this in the benchmarks below using the `.Find` method to find a specific element in a list.

![list-find-linear](https://res.cloudinary.com/aaron-bos/image/upload/v1673574868/list-find-linear_vtswgr.png)

## `Dictionary<Tkey, TValue>` and `HashSet<T>`

In this section, we are going to focus on a couple of hash-based collection types, which are `Dictionary<TKey, TValue>` and `HashSet<T>`. While these are different types they both rely on hashing algorithms to store and keep track of the elements that are contained inside their collections. As we look at manipulation and searching operations we'll see some similarities with `List<T>`, but there are also some key differences that make these hash-based types appealing in certain scenarios.

### Manipulating hash-based collections

Both `Dictionary<Tkey, TValue>` and `HashSet<T>` are unsorted collection types, just like `List<T>`. We can also expect these hash-based collections to perform similarly to lists when it comes to manipulating elements. The documentation states that when adding items from a dictionary or hash set without a defined `Capacity`, the operation will have a linear, or **O(n)**, runtime. If we have defined a value for `Capacity` and the `Count` value is less than the capacity when adding, the operation will be performed in constant time or **O(1)**.

Interestingly enough when I performed benchmarks of this data, I noticed that the `Add` method performed almost identically when explicitly setting the capacity and when not. I took a look at the source code for the `Dictionary` class [here](https://github.com/dotnet/runtime/blob/6aaaaaa5c7b1160a237bb381074e707c3ea1e9b4/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs#L473), which was quite interesting but a little challenging to follow while navigating in GitHub. For the dataset and benchmarks the `Add` method was performed in constant time.

![dict-add-benchmark](https://res.cloudinary.com/aaron-bos/image/upload/v1673574868/dict-add-benchmark_eurauo.png)

When it comes to removing elements from a dictionary or hash set, the operation is **always** performed in constant time. The reason for this is that the stored hashed values can be easily found in the underlying hash table for each of these collection types. Let's take a look at some benchmarks that confirm these behaviors and their runtimes. The example below shows the benchmark results for removing elements from `HashSet<T>`.

![hash-set-remove-constant](https://res.cloudinary.com/aaron-bos/image/upload/v1673575775/hash-set-remove-constant_pqew6h.png)

### Searching hash-based collections

We've seen some of the efficiencies that we can gain from using hash-based collections when manipulating data. Now we're going to look at their performance when searching for specific elements. There was one operation that we discussed previously that may provide a tip as to what the search performance might be...and that was the `Remove` operation. If we think about what needs to happen to remove an element from a hash-based collection, we first need to **find the element**, then we need to remove it. Searching is essentially the same operation without the removal, so if you remember that removal is performed in constant time we should be able to assume that searching is also performed in constant time or **O(1)**. Fortunately, that's a correct assumption as we'll see the runtimes approaching constant time in the following examples. The examples will show indexing into a dictionary and also calling `HashSet<T>.TryGetValue`.

![dict-index](https://res.cloudinary.com/aaron-bos/image/upload/v1673581722/dict-index_czkosn.png)

![hashset-trygetvalue](https://res.cloudinary.com/aaron-bos/image/upload/v1673581700/hash-set-trygetvalue_dvphan.png)

## Sorted Collections

So far we've looked at `List<T>`, `Dictionary<TKey, TValue>`, and `HashSet<T>` and how they perform different actions through the lens of big O notation. I wanted to take a quick look generally at sorted collections and their runtimes for the operations we've examined for previous types. Those operations are adding, removing, and searching each of the collections. One similarity between sorted collections and the ones discussed already is that the runtime is still O(n) when the internal capacity of the underlying data structure needs to grow due to the operation.

In most circumstances, we can expect sorted collections to perform operations in logarithmic time or **O(log n)**. This means that the runtime does change as the input size grows, but less drastically as the input size continues to grow.

![ologn](https://res.cloudinary.com/aaron-bos/image/upload/v1673664700/ologn_a8jdrn.png)

Although I haven't used sorted collections often in my day-to-day, I think it's useful to examine at least one benchmark to confirm their behavior, but also to be aware of their performance features. If there is a data set that we know will always be sorted, maybe it makes sense to use a `SortedList<TKey, TValue>` instead of a `List<T>`. Decisions always come with tradeoffs and being fully aware of the options and their implications is key to making the most correct decision. Let's take a look at the performance benchmarks for adding to and searching a `SortedList<TKey, TValue>` and confirm that we see close to logarithmic runtimes.

![sorted-list-add-get](https://res.cloudinary.com/aaron-bos/image/upload/v1673664773/sorted-list-add-get_cwxlfs.png)

The goal of this post wasn't to share the runtimes for each of these operations on the different collection types. That can be found easily in the documentation. The main goal was to present this information in a way that highlights the performance features of each operation and type in given scenarios. With this information, we should be prepared to choose the correct collection for any problem that is thrown our way.

If you'd like to check out any of the benchmark code, head over to this [repo](https://github.com/aaronmbos/dotnet-collections-big-o). If I'm being honest this was my first introduction to [BenchmarkDotnet](https://benchmarkdotnet.org/) and it was a great learning experience. While the benchmarks mostly represent the runtimes as expected, there may be some margin of error due to the way that the benchmarks had to be set up. Unfortunately performing very fast mutations isn't super simple to benchmark, so some of the setups for each benchmark run may be included in the executed times.


We use collections in our code daily, but do we ever step back and consider how they perform in the context of Big O Notation benchmarks? In this post, we'll examine the different collection types in .NET to see how their behaviors relate to well-known Big O notation functions. Let's dive in!

Hey! 👋

My name is Aaron Bos and this is my blog.

Recent Posts