agl-alexglopez / heap-allocator-workshop

This repository is a workshop for heap allocator implementations using a variety of data structures and algorithms. The goal is to compare performance and tradeoffs of different approaches in depth.

Hi there, I'm Alex 👋🏻

I'm a former English teacher turned perpetual student of Computer Science and Software Engineering.

What's New?

The Operating System

I recently finished implementing the well-known PintOS kernel and operating system in C. This was a fun and challenging endeavor, especially with some of Stanford University's unique requirements in implementation through the CS212 course offering. From this work I have found a new interest in developing low level libraries to make systems programming easier and more pleasant. These projects started as extensions to the base operating system provided libraries and have developed into libraries under active development.

• str_view - A string helper library providing read only string handling, searching, and tokenization in C (now available through vcpkg).
• tree-lib - An exploration of different data structures supported by various types of trees in C. This library will likely expand to encompass a more general suite of data structures with a wide variety of implementations.

What's Old?

Rust and The Terminal

In maze-tui, I explored how to stretch the capabilities of the terminal to create beautiful visualizations of common maze building and graph searching algorithms. With the help of ratatui.rs, I was able to realize my vision of interesting and unique algorithm visualizations in the somewhat constrained environment of the Terminal User Interface. Also, the maintainers for ratatui.rs were very helpful in guiding me towards best practices with their library in the Discussion section of their repository. Go check them out! Check out the rough draft C++ version that started it all.

Algorithm Exploration

I also enjoy exploring new and challenging algorithms and tweaking their core ideas to apply to new and interesting problems. That is the focus of dancing-links and dancing-links-and-planning-pokemon. What started as Stanford University assignments regarding recursion, vertex covers, and independent sets, turned into reworking these ideas to solve computationally difficult problems. This led me to connect Donald Knuth's Dancing Links algorithm to a wide variety of cover problems, even applying it to a beloved video game from my childhood. These projects are written in C++ and I am currently working on big changes for dancing-links-and-planning-pokemon, using this project as an opportunity to learn about the relatively new WebGPU API and the not so new OpenGL.

TCP

In the spring of 2023 I implemented a comprehensive version of the TCP Network protocol bottom to top; starting with the byte stream and ending with a peer to peer connection. The implementation and design principles I learned from the CS144 Stanford Networking course were invaluable. I won the end of quarter competition for most performant Reassembler and my combined ByteStream/Reassembler performance was second behind the course staff! Again, Stanford University requests we keep our solution private, but the repository we worked from is available publicly every year. Feel free to check it out and I'm happy to share my work upon request. Here is a teaser of a TCPReceiver/Reassembler diagram from my writeup on that section of the course.

                            \     TCPReceiver
                             \ +-------------------+
                              \|isn=0              |
                  +---+-----+                      |
>>>>>>>>>>>>>>>>>>|844|afdgh+>>>>>>>>>>>v          |
                  +---+-----+           v          |
                            \  |        v          |
                             \ |        v          |
                              \|        v          |
               +-----+------+           v
<<<<<<<<<<<<<<<|ackno|window|<<<<<<<<<<<<<<<<<<<<<<<<<<<
               +-----+------+           v              ^
                               |        v          |   ^
                               +-----   v  --------+   ^
                                        v              ^
                                 +--------+-----+      ^
                                 |844+2^32|afdgh|      ^
             \                   +--------+-----+      ^                       /
              \                         v              ^                      /
               \                        v              ^                     /
                \                                                           /
                 \                                                         /
                  |                                                       |-First Unacceptable Index-1000
                  |                                                       |
                  | Stored Segments-----------------|                     |
                  | Next Index Needed---|           |                     |
                  | Pushed Bytes--|     |           |                     |
Popped----|       |               |     |           |                     |
          |       |               |     |           |                     |
|-----------------|------------------|  |           |                     |
------------------+------------------+  |        |------------------------|
;asdkjf;laskjdls  | f8299fsdoiuosid8 |-[844+2^32] |[896+2^32]-->[940+2^32]|
------------------+------------------+                  8          s
                                                        a          8
                                                        y          l
                                                        8          n

                                                  Reassembler

What's Next?

Compilers

The black box of compilers has always been fascinating to my and I will finally have a chance to build a compiler, opening the box!