Subjunct: share your secrets
November 11, 2013
Yesterday I built Subjunct, a small web application that lets you share private messages.
You already have shared secrets (e.g. inside jokes) with your friends that can be used as passwords to secure information. Subjunct lets you use your existing shared secrets to communicate securely with other people, without requiring anyone to create an account.
As usual, the project is open source!
Markov chain domain names follow-up
October 31, 2013
Note: All of the domain names mentioned below were unregistered at the time of this writing.
I recently wrote a script to find unregistered .com domains (see this post for details). It builds a simple statistical model of the English lexicon and generates word-like strings according to that model. I let the program run for a few hours, and it generated thousands of unregistered domain names. The results were unexpectedly entertaining.
My favorites
Here are a few of the ones I especially liked:
antispicy.com brideweed.com dewdropping.com evilship.com honeysweetways.com milkgrower.com neckmold.com outjinx.com piewipe.com shakespearmaid.com speedboatman.com subpubic.com weirdlike.com
Could be real websites
The following domains seem to me like they could be actual startups, although I don’t know what these startups would do. Another description for this category is “domains that I think are worth more than their list price.”
blamework.com bordable.com cojustify.com factioner.com fribbly.com goosebeak.com harmproof.com hairsplice.com jawfall.com lowmeter.com mistag.com parabold.com pipewalk.com polycook.com punnable.com ruinproof.com songfulness.com stoplifted.com tipmost.com uglified.com voiled.com yardkeep.com
Found in a textbook
I must have trained the model on a rather technical dictionary, because many of the domains it produced sound like they came straight out of a textbook.
ganglionlike.com isoporic.com monozygous.com myotropism.com ozonomer.com phonozoa.com postasis.com protonometer.com scabiosis.com
Could be real words
A jillion of them seemed like they could be actual words, though they are not.
embowel.com introscopy.com isolatry.com pederate.com sejunctive.com varicate.com
Signal vs. noise
Some of these domains are better than others. For example, overfamed.com is probably worth more than subcollembolize.com. I would like to train a classifier, such as a support vector machine, on some hand-labeled examples and use it to filter out the bad names. What features would we give this classifier?
- Number of characters
- Number of vowels
- Number of Google search results
- Number of repeated characters
- ...
Hold on—I have an idea for a research project. Stay tuned!
Leaky abstractions
October 30, 2013
In my last post, I wrote a small Python script called
domain_finder.py which finds unregistered .com domain names. It worked pretty well, so I decided to move it into a folder where I archive my small projects.After moving it, I ran it again just for fun. But this time, it yielded a series of numbers before printing its real output:
$ ./domain_finder.py -102 -100 1 4 5 6 8 101 103 monial.com medinid.com <-- Available pluvious.com caribbed.com <-- Available infang.com ...
Where were those numbers coming from? I scanned the script for
print statements. There were only two:domain = word + ".com" if available(domain): print domain + " <-- Available" else: print domain
It clearly wasn’t those. So if I wasn’t printing those numbers, who was? I took a look at my imports:
from collections import defaultdict from random import random, choice from string import ascii_lowercase from subprocess import Popen, PIPE from time import time, sleep
Those are all from the standard library—they should just work, no matter what, right? But I knew it had to be one of them. I started removing them one by one. The numbers disappeared when I commented this one out:
from collections import defaultdict from random import random, choice from string import ascii_lowercase # from subprocess import Popen, PIPE from time import time, sleep
So,
subprocess was printing those numbers? Weird. That’s a widely used Python library—surely people would have complained about this before me. Something wasn’t right. I opened a Python shell and tested it out:>>> import subprocess -102 -100 1 4 5 6 8 101 103
Okay, at least there was nothing wrong with my script. So what’s
subprocess doing? Is my installation of Python broken? I Google’d around—nothing came up. Why would moving the script cause the program to change behavior? I looked in the directory for clues.$ ls domain_finder.py select.py merger.py
There were two other files, select.py (my linear-time implementation of the k-select algorithm) and merger.py (an algorithm I invented for a school project). It then dawned on me—select is a system call that is used to wait on file descriptors, and there is a corresponding Python module of the same name—and I bet it is imported by
subprocess.To test my hypothesis, I renamed
select.py to kselect.py. Sure enough, that fixed it.But this didn’t sit well with me. I never directly imported
select, and I only used modules in the standard library. My program should work anywhere. When you use the subprocess module, there is an unwritten rule that you are not allowed to have a file named select.py. Maybe I should have just not been stupid enough to name a file select.py, but does that mean I’m supposed to know the name of every module in the standard library before naming a script?Generating domain names with Markov chains
October 29, 2013
Coming up with good product names is a weakness of mine, and finding names that are available as .com domains is especially difficult. I wrote a small Python script that trains an n-gram Markov chain on the English lexicon, generates word-like strings according to that model, and checks if the strings are available as .com domains.
Here is some sample output:
$ ./domain_finder.py sibility.com caliology.com mandarch.com hopefulness.com spinical.com <-- Available! opinate.com motion.com synous.com torrency.com <-- Available! mullock.com genetic.com apophysis.com intrated.com <-- Available! calycule.com <-- Available! amido.com swiveless.com <-- Available! bajury.com <-- Available! tendother.com <-- Available! embole.com argasia.com stroot.com ...
The code uses the
whois command and the /usr/share/dict/words wordlist (both are available by default on Linux and Mac OS X installations).#!/usr/bin/python -O
from collections import defaultdict
from random import random, choice
from string import ascii_lowercase
from subprocess import Popen, PIPE
from time import time, sleep
# get a list of words with only ASCII characters
words = [w.strip().lower() for w in open("/usr/share/dict/words").readlines()]
words = [w for w in words if all([c in ascii_lowercase for c in w])]
words = ["^" + w + "$" for w in words if w != ""]
# construct a discrete-time markov chain of n-grams
n = 5 # this is the "n" in n-grams, try adjusting this for different results
transitions = defaultdict(lambda: defaultdict(float))
for word in words:
if len(word) >= n:
transitions[""][word[:n]] += 1.0
for i in range(len(word) - n):
gram = word[i : i + n]
next = word[i + 1 : i + n + 1]
transitions[gram][next] += 1.0
# normalize the probabilities
for gram in transitions:
total = sum([transitions[gram][next] for next in transitions[gram]])
for next in transitions[gram]:
transitions[gram][next] /= total
# sample a probability mass function (dict from elements to probabilities)
def sample(pmf):
sample = random()
cdf = 0.0
for e in pmf:
cdf += pmf[e]
if cdf >= sample:
return e
return choice(pmf.keys())
# generate a word according to the markov chain
def gen_word():
# start with a prefix
word = sample(transitions[""])
# wait until the markov chain adds a terminator to the word
while word[-1] != "$":
# append a new letter chosen according to the markov chain
gram = word[-n:]
if gram in transitions:
word += sample(transitions[gram])[-1:]
else:
word += choice(ascii_lowercase + "$")
# optional: allow multi-word domains
if word[-1] == "$" and random() > 0.7 and len(word) < 8:
word += sample(transitions[""])
# remove the boundary markers and return the word
return word.replace("^", "").replace("$", "")
# check whether a domain is available (e.g., "example.com")
# returns a bool indicating if the domain is available or None on timeout
def available(domain):
# use the "whois" command to determine availability
process = Popen(["whois", domain], stdout=PIPE, stderr=PIPE)
end_time = time() + 4.0 # timeout after 4 seconds
while time() < end_time:
if process.poll() is not None:
return "No match for" in process.stdout.read()
sleep(0.1)
try:
process.kill()
except:
pass
return None
# generate domain names forever
while True:
# generate a few words and pick the smallest
word = sorted([gen_word() for i in range(3)], key=lambda x: len(x))[0]
# report whether the domain is available
domain = word + ".com"
if available(domain):
print domain + " <-- Available"
else:
print domain
As always, feel free to use this for anything. See the follow-up post.
Region-based memory management
October 19, 2013
If I were to design a programming language, it probably would be very different from mainstream languages. Every day new wacky ideas about programming languages come to me—it’s an unhealthy obsession. Here’s what I was thinking about today.
Manual memory management
Before I spill the beans, let me give you some context. In the beginning, there was manual memory management, like in this C example:
// allocate a kilobyte of memory char* buffer = malloc(1024); ... // free the memory free(buffer);
For every call to
malloc, you need a corresponding call to free to release the memory back to the operating system. This is an annoying requirement, and sometimes software engineers forget to call free, resulting in memory leaks.Garbage collection
So a famous computer scientist named John McCarthy invented the garbage collector, which is a special program that periodically frees memory when you’re done with it so you don’t have to. So, for example, here is what the above example would look like in Java, a programming language with a garbage collector:
// allocate a kilobyte of memory byte[] buffer = new byte[1024]; ... // the memory is automatically released
Notice we didn’t have to deallocate the memory—but this comes at a cost. Garbage collectors can incur noticeable performance hits, especially if they are poorly written. For example, my cell phone runs Android, and I frequently notice my phone lock up for a few hundred milliseconds while the garbage collector reclaims unused memory. Applications that have real-time requirements (e.g., audio DSPs, games, operating systems, pacemakers, autopilots, etc.) typically do not use garbage collection, because the degradation in performance or lack of predictability is unacceptable.
Resource Acquisition Is Initialization
So do we have to revert to C-style manual memory management for these kinds of programs? C++ has a different solution to this problem, called Resource Acquisition Is Initialization (RAII). The idea is that objects allocate whatever memory they need in their constructor and release that memory in their destructor, which automatically runs when the object goes out of scope. Check this out:
// allocate a kilobyte of memory vector<char> buffer(1024); ... // the memory is automatically released
It looks a lot like garbage collection, right? But here the memory is released exactly when
buffer goes out of scope. So instead of a garbage collector which runs at unpredictable times and frees a large number of objects at once (which is slow), objects are automatically released one at a time, in a deterministic, predictable order, as they would be if you wrote it in C.Limitations of RAII
In RAII, heap-allocated memory is tied to the lifetime of an object on the stack. But if we’re doing that, why don’t we just allocate all memory on the stack? There are two issues with that:
- Maybe the stack isn’t big enough. A typical stack size is 8 megabytes. What if I want a gigabyte?
- Maybe I want the memory to outlive the current stack frame, e.g., I want to return it from a function.
RAII is a good solution to Issue 1. Does it also fix Issue 2? Not really—the whole point of RAII is that the memory is released automatically when the function returns. So if we held onto that memory after the function returned, when would it get released? C++ has some mechanisms (e.g., smart pointers, copy constructors, move semantics, etc.) to let you transfer ownership of that memory from the function call to the surrounding scope. But in my opinion, these non-orthogonal concepts are inelegant hacks that are only necessary because the language is poorly-designed (and overly complicated!), and they remind me too much of manual memory management. But what concerns me more is that using these workarounds is optional—the possibility of memory leaks still exists. What I want is a system where a) heap allocations are possible, b) memory leaks are fundamentally impossible (in the sense that we can easily pinpoint exactly where every piece of memory is released), and c) there is no unpredictable performance penalty due to a garbage collector running in the background. It’s easy to design a system with any two of these properties, but can we have all three?
Region-based memory management
Consider this code in a Java-like (call-by-sharing) language that does not have garbage collection:
int[] compute_big_array() {
int[] data = new int[1048576];
...
return data;
}
void foobar() {
int[] big_array = compute_big_array();
...
delete [] big_array;
}
Without garbage collection, it is the engineer’s responsibility to release
big_array at the end of foobar. We want to return the array from compute_big_array, so vanilla RAII can’t help us here.RAII ties heap-allocated memory to lexical scopes. But often times memory should be shared between multiple, unrelated lexical scopes. In the example above, an RAII-like approach to memory management would free
data when compute_big_array returns (perhaps after making a copy of it). But we want the original memory to be available to foobar after compute_big_array returns. So this memory shouldn’t be bound to the lexical scope of compute_big_array, but it also shouldn’t be tied to the lexical scope of foobar.Notice, however, that we only need the memory to exist during the execution of
foobar. But this may include calls to other functions defined elsewhere (in unrelated lexical scopes), and we may want to make the memory available to those functions as well. To use the domain lingo, we want the memory to be available in the dynamic scope of foobar. Can we design a system that ties the memory to this dynamic (not necessarily lexical) scope, guaranteeing that it will be freed when the program execution leaves that scope?Let’s come up with a new strategy that allows us to specify a dynamic scope for each memory allocation which dictates the lifetime of that memory.
int[] compute_big_array(MemoryAllocator<int> allocator) {
int[] data = allocator(1048576);
...
return data;
}
void foobar() {
MemoryAllocator<int> allocator = makeAllocator<int>();
int[] big_array = compute_big_array(allocator);
...
}
Here’s how it works. The language gives you a parametrically-polymorphic
makeAllocator function, that you can use to create a memory allocator (and the lifetime of this allocator is called a region). If you want to allocate some memory, you have to use an allocator. When an allocator goes out of scope (i.e., the program leaves the region), its destructor frees any memory that it allocated. Every variable goes out of scope at some point, so any memory you allocate is guaranteed to be freed. But unlike garbage collection, there is no extra performance penalty! It may be a little cumbersome to pass around memory allocators, but for some applications the strong safety guarantees make it worth it.Case study: a web server
Web servers are long-lived programs that serve web pages to clients, and it’s not uncommon for a web server to run continuously for months or longer. It is crucial that web servers do not leak memory, because otherwise they would quickly consume all available resources and crash. With region-based memory management, we can be sure that no memory is leaked from one request to the next, which is a stronger guarantee that most garbage collectors provide. Consider a simple single-threaded web server:
void main() {
while (true) {
MemoryAllocator<int> allocator = makeAllocator<int>();
// listen on port 80 and handle requests, using allocator as necessary
}
}
When the server is done processing a request, the allocator goes out of scope and all memory allocated for that request is deallocated. With most garbage collectors, you have no guarantees about when the collector will run and what it will free. So a) our web sever will have a tiny memory footprint, b) it is guaranteed not to leak memory from one request to the next, and c) it does not have the performance cost or unpredictability of a garbage collector.
Conclusion
Here are some cool things about region-based memory management:
- Regions cannot leak their memory to the outside world. All heap allocations are performed inside regions, so no memory is ever leaked.
- Often, when functions in C return pointers to memory, it’s not clear who is responsible for deallocating it. Systems based on regions do not have this problem: if a function allocates and returns memory, you have to provide it with an allocator that is responsible for this memory.
- There is no performance penalty due to a garbage collector running in the background. Memory allocation is deterministic and predictable.
- Writing a good garbage collector is hard. Writing a good region-based allocator is easy.
However, there are a couple of disadvantages as well:
- Region-based memory management requires more bookkeeping (you have to declare regions and keep track of memory allocators). This can be alleviated by having functions declare implicit regions around their bodies, and allocating memory to those regions by default.
- Sometimes, the lifetime of objects does not tie well to scopes—neither lexical nor dynamic. For example, consider a web server that needs some data to persist between requests, but that data grows and some of it needs to be freed occasionally (a memory pool might be a good solution to this). Another example is data that is shared between threads of a program.