When developing software, things you haven't thought of cause the most trouble. Just occasionally, a checklist (or ticklist for English readers?) can save the day.

Although “underlap” is a real word, I abuse it as a pun on “overlap”. An underlap is where there is a gap. “Mind the gap!” as they say on the London Underground.

I began using the term in 2006 with my Mind the Gap blog. Much later I adopted it as a Mastodon username and now as the name of this instance and its domain.

#SoftwareDevelopment

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

underlap

2024-12-20 03:35:38

writefreely

Privacy

This site does not collect any information about visitors except for the total number of views of each post.

If and only if you leave a comment, the blog securely records information to notify you of updates. For complete anonymity (without notifications), simply leave an anonymous comment by clicking on “ANONYM” under “Sign In”, or email me instead. For more details, see “Privacy” on remark42.

As part of the ActivityPub support, the blog records the ActivityPub identity of anyone who follows it, so they can be notified of new posts.

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

Remark42 – Privacy-focused lightweight commenting engine | Remark42

Remark42 is a self-hosted, lightweight, and simple (yet functional) comment engine, which doesn't spy on users. It can be embedded into blogs, articles or any other place where readers add comments.

^remark42.com

People get into software development these days via a number of routes, but they usually start with some form of computer, even if it's only a mobile phone, and the internet. Born in 1960, my route into software development was rather different.

Childhood

At primary school, I enjoyed playing with chemistry and electronics sets bought for birthdays and Christmas by my parents. My uncle used to give me old circuit boards (from his work in a weighing machine factory) which I would re-solder to create my own circuits. Another relative, a TV engineer, gave me a book on electronics with formulae I found at once fascinating and incomprehensible.

After enquiring at a library with my parents' help, I returned home with a book of mathematical tables. I think that was the beginning of my love of mathematics. I was by then frustrated by electronics as I couldn't easily predict how (analogue) circuits would behave and my only interest in chemistry was the occasional small explosion. But mathematical equations turned out to be fun to understand and manipulate.

My Dad's work in printing ([1]) meant I had a ready supply of paper for playing with algebra, trigonometry, and calculus picked up from “Teach Yourself” books. I don't know how children learn maths these days when so much is online. For me, working things out on paper was essential to becoming fluent in algebra.

In the 1970's, my parents bought me a Sinclair Cambridge calculator, which must have cost them over a week of my Dad's wage. I took their sacrificial generosity for granted, as children do. I used to spend hours on end with this in the school holidays, calculating logarithms and other formulae from Taylor expansions and comparing the answers to those in mathematical tables. Later I was bought a TI-58 programmable calculator and wrote some small programs of a very limited kind.

First exposure to programming

Part of my O level mathematics course was learning to write simple BASIC programs. Our teacher would collect our hand-written programs, walk over to the computing department at Leeds University near the school, key the programs in to the PDP-10 (fixing any syntax errors), run them, and hand out the output in the next lesson.

This led to a couple of summers when about 30 of us attended a solid week doing programming exercises on the university computers. A handful of us then opted to extend our access throughout the summer holidays.

I would spend whole days at a time programming, at first in BASIC, then Algol 60 and a little Algol 68. My favourite creations were games: noughts and crosses and star trek. The noughts and crosses program was extremely repetitive until I implemented some matrix transformations that greatly reduced the number of possibilities.

I remember thinking at the time that I could never do programming as a job because it was far too addictive.

For my A levels, I chose maths, further maths, physics and (mandatory) general studies as well as special papers in maths and further maths. I really couldn't get enough maths at that stage and my choice of university course was obvious.

University

I was very fortunate to study maths at University College, Oxford (selected because it was where the maths teacher, mentioned above, studied). In the third year, I chose some computing-related modules including computability, error-correcting codes, and a couple of denotational semantics modules.

The semantics modules were paticularly interesting. Dana Scott introduced us to domain theory and Joe Stoy showed us how to define the denotational semantics of programming languages.

I also took a short programming course offered by the university, but didn't really learn much from it.

Towards the end of my degree I did a fair amount of BASIC and some assembly language coding on a Sinclair ZX81. But I still thought of programming as an addictive hobby, rather than a career option.

As I approached graduation there was a lack of jobs in the UK. I had a choice of doing a doctorate, either at Edinburgh or Oxford, or of following a career outside academia. I felt I was ready to leave academia, so I warily applied for programming jobs.

After a few rejections I received job offers from GCHQ and IBM. Since GCHQ wouldn't tell me which department I would be working in, I opted to work for IBM at the Hursley laboratory, situated in parkland just outside Winchester in the UK.

Employment

I spent the first few years in IBM working on projects that were cancelled. I even managed to delete my first substantial piece of code by checking it into the library control system twice (interesting feature, that), which was probably a good thing considering the quality of my code.

I went on many programming and computer architecture courses. In one of the most helpful, Wayne Stevens explained the concepts of coupling and binding. Armed with his techniques, I was able to develop code with a decent structure and started to feel more competent.

My career as a software developer, that would last four decades, had really begun.

#SoftwareDevelopment #PersonalDevelopment#CareerPlanning #Mathematics

Footnotes:

1. Dad was bright enough to have gone to college, but his parents couldn't afford it, so he left school aged 14. For his national service, he served in the Fleet Air Arm of the British Navy and fondly remembered being taught the theory of flight. He later worked as an engineer, but lost an eye in an industrial accident and ended up working as a manual labourer in a chemical factory where my Grandfather worked. He became a charge hand, but resigned due to the stress of being responsible for workers in a dangerous environment. As an example of the kind of thing that happened, one day he was accidentally drenched in a chemical solution and had to strip to his underwear and be hosed down. He and I taught ourselves to play chess and some basic algebra while I was at primary school. Later in life, he taught himself how to program, wrote his own home finance package in BASIC, and was an early adopter of Linux.

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

home computer produced by Sinclair Research

^{Contributors to Wikimedia projects (Wikimedia Foundation, Inc.)}

underlap

2024-02-17 10:47:22

writefreely

What am I up to "now"?

(“Now” is in quotes as it depends on when I last remembered to update this page.)

Software

I'm prototyping multiplexing for servo/ipc-channel as a possible solution to the problem of it exhausting available file descriptors. I'm currently working out a design for managing the lifecycle of subchannel endpoints when they are transmitted over another subchannel.

Reading

I'm well into Cixin Liu's “The Three-Body Problem”. Not sure if the plot is really going to work yet.

See books for some of my past reads.

Listening

I'm enjoying Cal Newport's Deep Questions podcast. I occasionally listen to the Inspired podcast by Simon Guillebaud, which is an encouraging antidote to the current depressing themes dominating the news.

Exercise

To get back into running I'm on week 7 of the Couch to 5K app. I first used this app 15 years ago.

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

The Deep Life by Cal Newport : Podcasts

TDL is the online home of the Deep Life Movement, which argues for the importance of focus in a world increasingly deluged by distraction.

^{The Deep Life Podcast by Cal Newport}

List of posts in this series

I'm about to implement a piece of software and I thought I'd try an experiment. Rather than completing the implementation and writing a blog post afterwards, I'm going to blog my way through the entire process in the open.

I hope this will force me to adopt a more reflective approach and thereby learn some new things. I also hope that others will enjoy following along and perhaps even offer their insights and critique, in which case I'll provide open feedback.

What software?

To some extent, the experiment doesn't really depend on the particular piece of software, provided it is non-trivial. But I've chosen to improve the URL shortener I wrote about previously.

The current algorithm, while completely adequate for my practical use, has some unfortunate properties. In particular, the performance tails off badly as a large proportion of available shortened links is used up. Here's a graph that gives an indication of the problem:

Why a URL shortener?

I'm no application developer, so I've chosen something which is essentially a stand-alone algorithm, and that will, hopefully, have a simple interface.

Some have argued that link shorteners are unnecessary, or are a bad thing. They may be right, but that's not the point. I think this piece of software will have enough “bite” to be interesting, but will also be fairly tractable for me to implement on my own.

The real point is for me, and any readers, to have some fun and hopefully learn something along the way.

What's the problem?

There is a design issue in the current algorithm: a URL suffix is chosen at random from some 26,000 possibilities, but if the chosen suffix has already been used, the choice needs to be repeated. Once a large proportion of the 26,000 possibilities is in use, there is a high probability of failure and a very high CPU cost per shortening request (think denial of service).

Next steps

I want to set the scene properly. In the next post, I'll write up the maths behind the graph. You can certainly skip this piece if you have a maths allergy.

I'll then start to look for a better algorithm. For example, varx/tech suggested using “a small-domain cipher” such as a Feistel cipher in CTR mode (no, I hadn't heard of this either, until I followed the link). I'll want to understand and explain the algorithm before getting into coding. I'll also want to think about how to test the thing properly.

Then I'll set about coding the algorithm, almost certainly in Rust (one of my favourite languages) and definitely in the open under an open source license.

I suspect I'll want to plug the algorithm into the existing code, but in such a way that alternative algorithms can be used in future. The idea is to come up with a usable, testable interface to the set of possible algorithms. So designing a suitable interface, in Rust, will be part of the challenge.

A warning

I'm not in a rush and I have some holidays coming up, so this series of posts won't necessarily appear on a predictable schedule. I'll use the tag #OpenDevelopment to tie together the posts.

An invitation

Like I said, I want this to be done in the open. So if you already have feedback, I'd love to hear it. You can contact me using the link below.

#OpenDevelopment #SoftwareDevelopment #Rust

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

underlap

2024-07-25 19:54:21

writefreely

Self-hosting a Rust link shortener

Following Google's dead-ending of their link shortener, I decided it was time to wean myself off the proprietary bit.ly in favour of a self-hosted solution. I posted this on Mastodon:

Anyone know of a decent URL shortener written in Rust that produces URLs on a custom domain? Web UI, small memory footprint, and no tracking required.

I previously used bit.ly, but figured it is time to wean myself off proprietary URL shorteners.

Note: several implementations delegate to well-known shorteners, but I'm looking for something self-contained.

Ariel Richtman offered his turl as a starting point. It shortens each URL to a substring of the SHA-256 hash of the URL.

Anachron suggested using chhoto-url.

Others suggested implementations in languages other than Rust, but I prefer the security and relatively small memory footprint of Rust servers.

Given that chhoto-url supported persistence and turl didn't, I decided to take that as a starting point.

But some people thought link shortening was an anti-pattern. Let's discuss that first.

Why use a link shortener?

My use cases are where I want to be able to remember a long link or for me or others to be able to type in a link easily.

I don't use shortened links very much and, when I do, they are typically pointing at ephemeral content, so it doesn't matter if the shortened link becomes unavailable after a year or two.

Self-hosting chhoto-url

I prefer not to use Docker (which was recommended in the README), so I built the code on Linux ready to run directly on my VPS:

git clone https://github.com/SinTan1729/chhoto-url.git
cd chhoto-url
cargo build --release --manifest-path=actix/Cargo.toml

I then copied the binary and the resources directory to the /var/www/chhoto-url on my VPS. I created an empty database file there too:

touch /var/www/chhoto-url/urls.sqlite

I used systemd to run the chhoto-url executable under its own user, passing three environment variables:

password=...
site_url=https://lk.underlap.org
db_url=/var/www/chhoto-url/urls.sqlite

Finally, I set up NGINX to delegate to the new server:

server {
    listen 443 ssl;
    server_name lk.underlap.org;
    location / {
        proxy_pass http://localhost:4567;
    }
}

(The support for my robots.txt file, enforced by my nginx_robot_access NGINX module, is not shown.)

This seems to work pretty well. Try this shortened link, for example: lk.underlap.org/great-curran.

What next?

I can see a couple of improvements that I'd like to make. Firstly, the words used to build short URLs seem unnecessarily long. So the constructed links are not particularly short, even if they are fairly memorable.

Secondly, there is a design issue in the algorithm, although it will work just fine for my purposes. The problem is that a URL suffix is chosen at random from some 26,000 possibilities. If the chosen suffix has already been used, the request fails and it's up to the user to try again. The usability of this is poor, but automating the retry could consume a lot of CPU. Once a large proportion of the 26,000 possibilities are in use, there will be a high probability of failure, and a very high CPU cost per request (think denial of service) if the retry was automated.

If there are n possible shortened URL, the number of attempts in shortening all n URLs using the above algorithm turns out¹ to be nHₙ where Hₙ is the nth Harmonic number (the sum of the reciprocals of all the numbers in the range 1..n).

When n is 26,000, the total number of attempts is over 279,000, since H₂₆₀₀₀ , is approximately 10.743. Another way of putting this is that, on average, each shortened URL needs just over 10 attempts.

Although the average number of attempts to shorten a URL successfully is more than 10, the number of attempts remains low until fewer possibilities remain, and then it rises rapidly as shown in this graph:

Thankfully there are better algorithms. For example, varx/tech suggested using “a small-domain cipher” such as a Feistel cipher in CTR mode (no, me neither, until I followed the link).

I'm lazy, but I also don't like code with design issues, so I suspect I'll make time to implement a better algorithm at some point in the future.

#colophon #mathematics #Rust

Footnote:¹ The number of attempts required when k out of n shortened URLs are already taken is n/(n-k). The total number of attempts for shortening n URLs is the sum of this term with k ranging from 0 to n-1, and that turns out to be nHₙ. If you'd like more detailed working, let me know.

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

turl

Tiny URL

^Codeberg.org

gource is one of my favourite programs. It produces a video animation of how a source code repository evolved and who worked on it. But, even with filenames and users hidden, the output is often beautiful and fascinating.

The initial phase of coding, even if it starts with a “dump” of existing code into version control, often shows intense rework and the creation of multiple directory structures. Major refactorings appear as explosions of global activity. The evolution slows down dramatically as a project enters its maintenance phase and less energy is expended.

For projects I've worked on, the explosive phases are those in which the most development effort was expended and when there was perhaps the most innovation and excitement.

Each of the examples below provides a screenshot of the animation and a link to download the video.

Cloud Foundry Java Client

This project provided a Java client for the Cloud Foundry API. It was led by Ben Hale who set and maintained an extremely high level of coding standards and uniformity. The code itself was a fascinating application of Project Reactor in the functional reactive programming style. I have often described the code as “crystalline” in structure.

Download the animation (537 MB).

systemd

A much larger project is the systemd init system for Linux. I know nothing about the internals of systemd, but the number of contributors and the scale of what appears to be refactoring at various points in the project are staggering.

Download the animation (476 MB).

Glasgow Haskell compiler

GHC is another long-standing, mega-project whose internals I know little about. However, there are clearly delineated sections of code, such as runtime library, backend, and test cases which continue to evolve at pace in the animation. This is due in part to the GHC community's focus on research and consequent avoidance of strict backward compatibility.

Download the animation (2.7 GB). Since it is particularly massive, you may prefer to recreate the animation yourself (see below).

Bindgen

rust-bindgen generates Rust FFI bindings to C/C++ code. I contributed a small patch to this code when I was developing a JVMTI agent in Rust and I was struck by the beauty and sophistication of the code. I am grateful to Nick Fitzgerald for coaching me through the development of the patch.

Download the animation (549 MB). This time I didn't hide the filenames as this gives a better understanding of the structure (including a substantial test suite).

Image relocation

image-relocation is a fork of a small project I initially developed with contributions from a few others. It's a utility for copying Docker and OCI images. After the initial development phase it was maintained by a couple of others.

Download the animation (231 MB). I didn't hide anything as the number of files and directories is modest and it shows the handover to maintainers and the fork.

Eclipse Virgo

Finally, Eclipse Virgo is a modular server runtime based on OSGi. The fireworks here are dramatic and, especially for those of us who worked on the project, the fine structure is fascinating.

Download the animation (479 MB).

Create your own

Once you've installed gource, depending on your platform, it's often possible to view an animation by cloning a repository and running gource from inside the cloned directory.

The videos above were produced on Linux using variations of the following command line:

gource --hide dirnames,files,users -s 0.01 -o - | ffmpeg -y -r 60 -f image2pipe -vcodec ppm -i - -vcodec libx264 -preset ultrafast -pix_fmt yuv420p -crf 1 -threads 0 -bf 0 gource.mp4

#SoftwareDevelopment #git

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

underlap

2024-02-17 08:28:38

writefreely

Contact

You are warmly welcomed to drop me a line or comment on a post by email, by using the comment facility at the bottom of each post, or by searching for or mentioning @mastodon@underlap.org on Mastodon (except when I'm fasting from social media!). You might even want to sign the guest book.

Also, please feel free to send me suggestions for topics you'd like me to write about.

And don't be shy. I'm delighted when people correct my spelling or grammar. I find it helpful when people express contrary views. Or if you just want to say “hello”, that'd be great.

Looking forward to hearing from you, Glyn

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]

---

Feedback: email me.

Comments (privacy)

[ ∪ | about | 🧻 | contact | 📖 | now | 🔍 | subscribe | © ]