Thursday, October 17, 2013

The worst notational abuse

I have lately been reading Programming Distributed Computing Systems: A Foundational Approach, by Carlos A. Varela, and so far been fairly impressed. The presentation has been clear, and the topics (the $$\pi$$ calculus, actors, the join calculus, and mobile ambients) are things that I probably should already know more about than I do. But it has reminded me of the worst abuse of notation I am aware of, in theoretical computer science.

In the $$\pi$$ calculus, computation occurs by processes exchanging messages across channels. Creating a channel (roughly the equivalent of introducing a new variable in a $$\lambda$$ expression in that calculus) is done with the syntax:

$$(\nu c)P$$

where $$c$$ is the new channels's name and $$P$$ is the remainder of the process, where $$c$$ is bound.

What is the Greek letter $$\nu$$? Nu. New $$c$$, geddit?

Sigh.

Saturday, October 12, 2013

A faster hashmap in Rust

If you take a look at the most recent Letterpress cheating in Rust results, you may notice something odd: Python, an interpreted, "scripting" language, is faster (or at least not slower) than Rust, a "systems" language that compiles to raw, executable, machine code. The head-to-head comparison is between alternatives/presser_three.py, taking 6 seconds, and anagrams-hashmap, currently taking 7.2 seconds. There are several reasons for this.

First, most of the Python code is actually optimized C. The implementation of the combination generator is in C (check around line 2291), and the dictionary (/hashmap/hashtable; this data structure has a lot of names) is a very important part of Python and is heavily optimized C. (dictobject.c, dictobject.h, dictnotes.txt)

Second, the Rust standard library's hash module implements SipHash 2-4, a cryptographically strong keyed hash.

Why is SipHash good (and coincidentally, why is Rust using it)? If you used, say, a non-cryptographically-strong hash as part of a hashmap to store HTTP request headers or parameters from a HTTP POST in an HTTP server, a denial of service attack can be very effective, simply by inserting a bunch of headers or parameters which hash to the same bucket and thereby make your hashmap behave like a very expensive linked list. A strong keyed hash avoids that, by making it difficult to predict what is going to hash to the same bucket. And, SipHash is a good strong hash function.

(Some notes on that link: "pyrhash" is reportedly "Python's new randomized hash, with a 128-bit key and 64-bit output", which may-or-may-not be the same hash function that is enabled by Python's -R argument (see the bug discussion). The weird part is that, according to my measurements, Python with -R is as fast as Python without -R, which may-or-may-not mean that the measured implementation of SipHash is faster than Python's default hash function.)

So, why is SipHash bad? If you ignore that last paragraph (which seems entirely ignorable for the moment), SipHash is fairly slow in comparison to a normal, weak hash function. According to my quick and dirty benchmark, it is about 2.6 times slower than my favorite DJB hash function, in fact. The DJB hash function has a long history and is both simple and fairly decent. Neatly, D. J. Bernstein is the "DJB" in djbhash, and also is a co-author of SipHash.

Fair enough. What happens if we replace SipHash with djbhash in Rust's hashmap? Well, unfortunately, it is not that simple. Replacing the default, SipHash, implementation of the Hash trait seems to make the Rust compiler unhappy. The default implementation is based on another trait, IterBytes, which gives access to the raw bytes of the to-be-hashed data; anything that implements IterBytes also gets the Hash trait. If you provide an implementation of Hash for your new data type without implementing IterBytes, you receive a complaint about not implementing Iterbytes. If you do implement IterBytes as well, you get a complaint about multiple implementations of Hash. As a result, replacing SipHash means replacing Rust's HashMap implementation as well.

A DJB hash

The djbhash function itself is tiny, but the translation into Rustic expands it a bit. This code is also a bit more flexible than the bare implementation, because it uses the IterBytes trait itself, to simplify the interface.

struct DJBState { hash : u64 }

impl DJBState {
fn new() -> DJBState { DJBState { hash : 5381u64 } }

#[inline]
fn djbhash<T:IterBytes>(t : &T) -> u64 {
let mut state = DJBState::new();
t.iter_bytes(true, |b| { state.write(b); true });
state.flush();
return state.hash();
}

fn hash(&self) -> u64 { self.hash }
}

impl Writer for DJBState {
#[inline]
fn write(&mut self, buf : &[u8]) {
let len = buf.len();
let mut i = 0;
while i < len { self.hash = (33u64 * self.hash) ^ buf[i] as u64; i += 1; }
}
fn flush(&mut self) { }
}


The values 5381 and 33 are magic, experimentally determined numbers in djbhash; you are not expected to understand them. The write method also uses a non-idiomatic style of iteration simply because it is slightly faster, according to my measurements.

The basic interface here is:

  let hash = DJBState::djbhash(str);


The Writer implementation and the new and hash methods would be useful to hash multiple values but for the simple cases I need can be entirely encapsulated by djbhash.

A faster HashMap

For the hashmap itself, I decided to go more or less all out, using the Python dictionary implementation as inspiration. Aside from the code linked above, my references were a StackOverflow question, a blog post by Laurent Luce, and a pure Python implementation. You may want to read those before going further, particularly if you want to flame me for not knowing what I'm doing.

The HashMap struct itself has four main entries:

pub struct HashMap<K,V> {
table      : ~[Entry<K,V>],
capacity   : uint,
length     : uint,
ghosts     : uint,
}


table is the primary vector of entries containing the contents of the map. capacity is the number of elements in table; one invariant of this structure is that capacity, and the size of the vector, are powers of 2. mask is a bitmask used to turn a hash value into an index into table; because of the power-of-two invariant, it is simply capacity - 1. Both capacity and mask can easily be calculated, but for the moment I have kept them because they are used frequently. length is the number of key/value pairs stored in the HashMap. ghosts is the number of slots that have had entries removed but have not been reused; it is used to ensure that table has some empty slots.

The Python dictionary and this HashMap use open addressing; all of the key/value pairs are stored in the table itself, rather than being linked off of a bucket. As a result, probing for a key in the map may involve multiple references into table, if multiple keys hash to the same slot index. In that case, a new index is calculated and the probe moves to that entry, a process called "chaining".

The Entry structure is important to understanding the implementation. Originally, I simply used Option, but that becomes problematic when key/value pairs can be removed; if you simply replace a removed pair with None, you lose the information that this slot is part of a chain with multiple keys hashing to the same index.

Table entries

enum Entry<K,V> {
Empty,
Full(K,V),
Ghost(K),
}


An Empty slot has never had an occupant. A Full slot has a current occupant. A Ghost slot (referred to in the Python implementation as a "dummy") is a key/value that has been removed; the key is kept to make probing faster in the case of probing for a value which was in the HashMap.

The primary method associated with Entry is matches:

impl<K : Eq, V> Entry<K,V> {
fn matches(&self, key : &K) -> bool {
match *self {
Empty                        => true,
Full(ref k,_) | Ghost(ref k) => k == key,
}
}
}


A key matches an Entry if the key could be inserted into the map in this Entry. An Empty Entry could be replaced by any key/value pair, so matches any key. A Full Entry matches its specific key. And a Ghost matches if the key that was in the slot is equal to the probed key.

Which brings me to probing....

Probing

impl HashMap {

fn probe(&self, key : &K) -> uint {
let mut free = None;
let mut hash = DJBState::djbhash(key);
let mut i = hash & self.mask;
while !self.table[i].matches(key) {
if free.is_none() && self.table[i].is_ghost() { free = Some(i); }
i = ((5 * i) + 1 + hash) & self.mask;
hash = hash >> PERTURB_SHIFT;
}
if self.table[i].is_full() || free.is_none() {
i as uint
} else {
free.unwrap() as uint
}
}


Probing a hashmap is the process of identifying which slot a given key is, or should be, located in. Probing is a three-step process:

1. Compute an initial slot, i. That is done by the two lines:

        let mut hash = DJBState::djbhash(key);
let mut i = hash & self.mask;

2. If the slot does not match the key, compute the next slot i in the chain. If a Ghost entry is seen during this process, remember it (as free). Repeat as necessary until a slot matches. This computation is done by the two lines:

        i = ((5 * i) + 1 + hash) & self.mask;
hash = hash >> PERTURB_SHIFT;


Note three things about this code: First, the use of hash (and the right-shift of hash) allows all of the bits of the hash value to enter the chain computation. Second, hash will eventually be zero, following the right shift, and $$(5i + 1) \mod\ 2^n$$ by itself will cycle through all of the values between 0 and $$2^n$$, so an empty slot is guaranteed to be found, if one exists. Third, the order of slots searched will always be the same for a given key, but two keys that happen to hash to the same slot will likely search a completely different chain of slots.

PERTURB_SHIFT is an experimentally-determined 5, by the way.

3. There are three possibilities when a matching slot is found:

• Slot i is Full (and its key is equal to the probed key): return i.
• Slot i is Empty and no Ghost slot was seen: return i.
• Slot i is Empty and a Ghost slot was seen: return the free Ghost slot.

Containerization

The next steps in writing HashMap are to implement some traits. Container (which supports len() returning length) is trivial; Mutable (providing clear to empty a map) only a little less so. Oddly enough, Map<K,V> is also pretty simple:

impl<K : Eq + IterBytes,V> Map<K,V> for HashMap<K,V> {
fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
let i = self.probe(key);
match self.table[i] {
Empty | Ghost(_) => None,
Full(_, ref val) => Some(val),
}
}
}


The only non-trivial part is that the Full pattern has to match val by reference, so it can be returned as a reference with the right lifetime.

MutableMap<K,V> is the only remaining trait, which requires three methods: swap, pop, and find_mut. find_mut is identical to find, with the exception that it matches the value by mutable reference: Full(_, ref mut val).

Until this point, this implementation in Rust has been, well, normal. I have treated Rust as sort of a combination of C and ML or OCaml, casually, and with relative impunity. But pop is where things start to get interesting. The pop method is used to remove an entry from the HashMap, which takes some finagling.

    fn pop(&mut self, key: &K) -> Option<V> {
self.expand();
let i = self.probe(key);
let (result,replacement) = match util::replace(&mut self.table[i], Empty) {
Empty     => (None,Empty),
Ghost(k)  => (None,Ghost(k)),
Full(k,v) => {
self.length -= 1;
self.ghosts += 1;
(Some(v),Ghost(k))
},
};
self.table[i] = replacement;
result
}


Ignore self.expand() for the moment; I'll get to it in a bit. The first important thing this code does is util::replace(&mut self.table[i], Empty): swap out the current entry in self.table[i] for Empty, returning the original entry. Then the method examines the original value to determine the result of the method and the actual replacement value that goes in table[i].

• If the entry is Empty, the key is not in the map; the return value is None and the entry should stay Empty.
• If the entry is Ghost(k), either matching the key or not (as seen in probe), the key is not in the map; the return value is None and the entry should stay Ghost(k).
• If the entry is Full, however, it needs to be removed. The length is decremented, ghosts is incremented, Some(v) is returned, and the entry is set to Ghost(k).

The swap-out is necessary because, in the Full case for example, I would be moving the k and v values out of the existing entry, leaving it in an indeterminate, unsafe state. The unsafe state would only be temporary, but the compiler's guarantees will not let me do it. Fortunately, I can use Empty as a placeholder.

The final method is swap, used to insert values.

    fn swap(&mut self, key: K, value: V) -> Option<V> {
self.expand();
let i = self.probe(&key);
match self.table[i] {
Empty => {
self.table[i] = Full(key,value);
self.length += 1;
None
},
Ghost(_) => {
self.table[i] = Full(key,value);
self.length += 1;
self.ghosts -= 1;
None
},
Full(_,ref mut v) => {
Some( util::replace(v, value) )
},
}
}


Replacing an Empty slot increases length; replacing a Ghost increases length and decreases ghosts, and replacing a Full involves replacing the value of the entry while returning the original value, again using util::replace to return the old value.

Maintaining invariants

So far, I have mentioned two invariants of the HashMap: the size of table is a power of 2, and table has at least one Empty element. Maintaining those invariants is the responsibility of expand, in two cases: adding new entries to the map, potentially requiring an increase in the table size, and removing elements, leaving Ghost entries.

    fn expand(&mut self) {
if self.length * 3 > self.capacity * 2 {
// Expand table if live entries nearing capacity
self.do_expand( self.capacity * 2 );
} else if (self.length + self.ghosts) * 3 >= self.capacity * 2 {
// Rehash to flush out excess ghosts
self.do_expand( self.capacity );
}
}


Those two cases form the two branches of expand. In the first case, if length is greater than 2/3 of capacity, the table size is doubled (this is from Python). In the second, if length + ghosts is at least 2/3 capacity, the size is kept, but the table is rehashed.

Performing the expansion or rehashing is handled by do_expand (and a lovely name that is, too).

    fn do_expand(&mut self, new_capacity : uint) {
let mut new_tbl = HashMap::with_capacity( new_capacity );
for elt in self.table.mut_iter() {
match util::replace(elt, Empty) {
Full(k,v)        => { new_tbl.insert(k,v); },
Empty | Ghost(_) => { },
}
}
// Copy new table's elements into self.  Note: attempting
// to do this more directly causes: "use of partially moved
// value"
let cap = new_tbl.capacity;
let len = new_tbl.length;
let ghosts = new_tbl.ghosts;
self.table = new_tbl.table;
self.capacity = cap;
self.length = len;
self.ghosts = ghosts;
}


do_expand simply creates a new HashMap of the right size and moves the Full elements to the new table, using util::replace to swap them out of the original table. Then, it copies the new table's fields into self, being careful not to leave self or new_tbl in a state the compiler would regard as unsafe until after it is safe to do so.

And that's all. The constructors, with_capacity and new, simply set up the structure, initializing the invariants with

        let capacity = uint::next_power_of_two(sz);


Results

A version of anagrams-hashmap built to use djbhash runs in approximately 3 seconds, half of the time of the standard library HashMap and the Python version.

The code for the faster hashmap is on Github.

Sunday, October 6, 2013

Letterpress cheating in Rust 0.8

Following the recent release of Rust 0.8, I have updated my ports of Jeff Knupp's Creating and Optimizing a Letterpress Cheating Program in Python and re-executed the crappy benchmarks.

As a reminder, this program looks for all of the words that can be made from a given set of letters, based on the system dictionary. The argument for all of these runs was "asdwtribnowplfglewhqagnbe", which produces 7440 results from my dictionary; I get 33,554,406 combinations out of those letters. I used Python 2.7.3; gcc 4.6.3 with -O3; and rustc 0.8 with -O.

Results

Language Program Rust 0.6
Duration
(seconds)
Rust 0.7
Duration
(seconds)
Rust 0.8
Duration
(seconds)
Python alternatives/presser_one.py 49.1 48.6 47.8
Python alternatives/presser_two.py 12.8 12.6 12.3
Rust anagrams-vectors-wide 11.8 13.1 12.2
Rust anagrams-hashmap-wide 9.3 15.4 12.1
Rust anagrams-vectors 8.0 8.2 11.9
Rust anagrams-hashmap-mmap 4.8 10.6 7.3
Rust anagrams-hashmap 6.0 35.5 7.2
Python alternatives/presser_three.py 6.0 6.3 6.0
C alternatives/anagrams-vectors 8.0 5.8 5.8
C alternatives/anagrams-hash 0.9 1.0 1.0

The big winner here, and the only obviously important change, is anagrams-vectors-tasks, which has steadily gone from hideously slow, to decent-ish, to pretty nice. This version of the program copies the entire dictionary to 6 worker tasks and then sends batches of combinations from the input string to each worker, which use binary search to look for the combinations. This and the -wide programs are the only multi-threaded versions, and the -wide versions, which divide the dictionary and have each worker look for all combinations, are much less chatty. As a result, I suspect inter-task communication has gotten much faster. Yay!

Changes

The primary change is that for expressions now use the new external iterator protocol, although not all of the iterator functions in the standard library have been updated. (Specifically, I couldn't find a new-style iterator over the lines of a file.) Given this change, and my previous post, I have modified each_combination to a style usable with do expressions.

Speaking of do, the times() method in the num::Times trait now uses that protocol instead of for.

The Clone trait now replaces Copy, and calls for a clone() method rather than the copy keyword.

There have been some miscellaneous library changes; uint::range has been replaced by iter::range (and there is some fancy type-system magic behind that). num::sqrt has replaced float::sqrt in complex.rs, the example of operator overloading. The mmap.rs module used by anagrams-hashmap-mmap is obsolete, since a cross-platform version is now available in os::MemoryMap. I have continued to use my module, since it serves as an example of the foreign function interface.

The FFI itself has changed, requiring #[fixed_stack_segment] and suggesting #[inline(never)] for calling C functions. The declaration of C functions no longer needs unsafe, which they are assumed to be. The C string interfaces have changed, although the interface is not much different; filename.with_c_str instead of str::as_c_str(filename).

There still seems to be a problem with the lifetime of temporary values. If I write the following code:

    for key in sorted_keys(dict).iter() { ... }


I then get something like the following error:

mk_anadict.rs:40:8: 40:26 error: borrowed value does not live long enough
mk_anadict.rs:40     for key in sorted_keys(dict).iter() {
^~~~~~~~~~~~~~~~~~
mk_anadict.rs:43:4: 43:5 note: borrowed pointer must be valid for the method call at 43:4...
^
mk_anadict.rs:40:8: 40:33 note: ...but borrowed value is only valid for the method call at 40:8
mk_anadict.rs:40     for key in sorted_keys(dict).iter() {
^~~~~~~~~~~~~~~~~~~~~~~~~


However, if I give the temporary value a name then everything works as expected:

    let skeys = sorted_keys(dict);
for key in skeys.iter() { ... }


Oh, and SipHash is still slow.

Saturday, October 5, 2013

Rust 0.8: External iterators

If you have browsed through my ridiculous Rust posts, you will know that I have been using a sad, silly combinatorics problem that I stole from someone else's blog to play with the programming language Rust. I am still doing it, I'm sorry to say.

If you have been following the development of Rust, you will know that between 0.6 and the recent release of 0.8, Rust's for expressions have changed from an "internal" iterator basis to an "external" iterator basis. (I've described the change before, way back when 0.7 was released. Geeze, that was a long time ago.)

Basically, an "internal" iterator involves a higher-order function that is passed as an argument a new function that represents the body of the for expression. This new function is called once on each element of whatever is being iterated over. An "external" iterator is instead an implementation of the trait Iterator, which means that it has a next() method. External iterators have many advantages, such as more flexibility and better composability, which is why the behavior of the for expression was changed. However, external iterators also seem to have downsides.

This is part of my implementation of an external iterator for generating all permutations of the contents of a vector:

impl<'self,T:Clone> Iterator<~[T]> for PermutationIterator<'self,T> {

#[inline]
fn next(&mut self) -> Option<~[T]> {
if self.initial {
self.initial = false;
} else if self.length <= 1 {
return None;
} else {
// find largest k such that indices[k] < indices[k+1]
// if no such k exists, all permutations have been generated
let mut k = self.length - 2;
while k > 0 && self.indices[k] >= self.indices[k+1] { k -= 1; }
if k == 0 && self.indices[0] > self.indices[1] { return None; }
// find largest l such that indices[k] < indices[l]
// k+1 is guaranteed to be such
let mut l = self.length - 1;
while self.indices[k] >= self.indices[l] { l -= 1; }
// swap indices[k] and indices[l]; sort indices[k+1..]
// (they're just reversed)
self.indices.swap(k,l);
self.indices.mut_slice(k+1, self.length).reverse();
// fixup permutation based on indices
for i in range(k, self.length) {
self.permutation[i] = self.values[ self.indices[i] ].clone();
}
}
return Some(self.permutation.clone());
}
}


The algorithm for generating the permutations (in lexical order) is straight out of the Wikipedia page, with the modification that it is working on an internal vector of indices rather than the data vector (to avoid potentially expensive copies). What I want to discuss is the line

        return Some(self.permutation.clone());


permutation contains the current permutation being generated by the iterator. It is intended to be passed directly to the body of the loop, which would avoid an allocation and data copies. Unfortunately, this code calls clone() there.

The reason it calls clone() is that this code implements an Iterator<~[T]> and therefore has a return type of Option<~[T]>. In other words, it returns an owned vector; hence the clone(). What I think I would like to do is:

// impl<'self,T:Clone> Iterator<&'self [T]> for PermutationIterator<'self,T> {

// fn next(&mut self) -> Option<&'self [T]> {
// ...
// return Some(self.permutation.slice_from(0));
// }
// }


Unfortunately, I cannot convince the compiler to let me return a borrowed reference to the permutation vector, which is an element of the PermutationIterator structure and should have the same lifetime1. On one hand, it should work, I think. On the other, well, maybe it is a sketchy thing to do.

Why is this important? Time to break out a performance comparison:

VariationTime (seconds)
vec permutations_iter11
vec permutations_iter (manual)7
lexical iterator6
old each_permutation1.2

These timings are for generating all 39,916,800 permutations of a vector of 11 integers, counting the number of permutations.

vec permutations_iter is the iterator version currently in the vec module, based on the Steinhaus–Johnson–Trotter algorithm. It allocates and copies the returned permutation as well.

vec permutations_iter (manual) is based on a suggestion from the implementer of the vec iterator (from the commit message introducing the S-J-T iterator); it does not copy the permutation, but iterates over element swaps from the permutation state space and lets the body of the loop update its own copy of the permutation. The code looks like:

    let mut v = do vec::from_fn(VECTOR_SIZE) |i| { i };
let mut count = 0;
for (a,b) in vec::ElementSwaps::new(VECTOR_SIZE) {
v.swap(a,b);
count = count + 1;
}
assert_eq!(count, NUM_PERMUTATIONS);


lexical iterator is my iterator above, also allocating and copying the return permutation.

old each_permutation is the previous permutation generator from the vec module. It used similar code to my iterator above, also based on the Wikipedia lexical generator algorithm. Critically, it does not allocate and copy the returned permutation; it is the "internal" iterator version.

The code for each_permutation can trivially be converted to be useful in a do expression, which may be the best option. It may be possible that this kind of generator is a bad fit for external iterators.

On the other hand, I am hoping that some very smart Rust developer will show up and tell me that, A), I'm an idiot, and B), there is a trivial way to do this that I'm not seeing.

Update

In the discussion on reddit, englabenny writes,

I'm surprised the manual ElementSwaps version performs so poorly. I didn't expect that. The premise of my Permutations Iterator was really that it could be implemented without copies -- which it could, but acrichto helped discover that was through a borrowchecker hole. So the fixed version that clones the whole vector for each iterator element is quite terrible.

Pull req: https://github.com/mozilla/rust/pull/9062 most of the discussion was on irc, and the initial copyless version isn't available, I'll pastebin it if git still has it somewhere.  Thanks git reflog: Buggy copyless permutations iter

In the discussion of that pull request, alexcrichton opened issue 9069, "Unsound behavior when returning &-pointers", writing,

I thought something like this should be a compiler error? It seems to me that the lifetime of b would conflict with attempting to re-borrow a as mut.

That would seem to imply that my desired behavior is wrong. That issue was marked as a duplicate of 8624, which seems to emphasize that changing the elements of a vector that potentially has an outstanding reference is a no-go.

In the same reddit thread, ericanderton suggested using managed vectors, which I had not thought about. It might work, but I'm stuck trying to dynamically allocate a mutable managed vector. And it still has the objection that mutating the iterated value is not entirely kosher.

Notes

1. For what it's worth, the error message is:

\$ rust build --opt-level 2 --lib combinatorics.rs
combinatorics.rs:62:20: 62:51 error: cannot infer an appropriate lifetime due to conflicting requirements
combinatorics.rs:62         return Some(self.permutation.slice_from(0));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combinatorics.rs:62:20: 62:36 note: first, the lifetime cannot outlive the expression at 62:20...
combinatorics.rs:62         return Some(self.permutation.slice_from(0));
^~~~~~~~~~~~~~~~
combinatorics.rs:62:20: 62:36 note: ...due to the following expression
combinatorics.rs:62         return Some(self.permutation.slice_from(0));
^~~~~~~~~~~~~~~~
combinatorics.rs:62:20: 62:51 note: but, the lifetime must be valid for the method call at 62:20...
combinatorics.rs:62         return Some(self.permutation.slice_from(0));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combinatorics.rs:62:20: 62:36 note: ...due to the following expression
combinatorics.rs:62         return Some(self.permutation.slice_from(0));
^~~~~~~~~~~~~~~~


Thursday, August 8, 2013

Quote o' the day: John Day and "But I'll never use this"

The following is from Patterns in Network Architecture: A Return to Fundamentals by John Day.

Good Solutions Are Never Obsolete

This illustrates why it is important to study good designs. Here we have used the Telnet half-duplex solution to solve what appears to be an either/or choice. Many students would complain about being taught the Telnet solution. "Why are we wasting time on this. Half-duplex terminals are a thing of the past. I will never need this!" Perhaps not, but as you have just seen, the form of the problem recurs, and so the same solution in a somewhat different guise can be applied.

I am a little sketchy on how the Telnet protocol applies to the problem he described, but this sidebar is a fine description why someone might want to spend some time learning to write sorting and searching algorithms or some of the common, basic data structures.