Hal might use slight traces of phrasing for a native Russian speaker — in small doses — to show increased degree of difficulty communicating in English. Wil curbs his vocabulary even more than usual.
Hal might chagrin Wil with slavish nods to tech fashion and/or convention. (The only Hal Wil knows is Hal Abelson, whose writing he respects. So no slight is intended toward anyone named Hal — Wil just needs an obtuse foil. But the story about this Hal is mostly true.)
Wil found himself in unexpected conflict with Hal over a simple LRU replacement for old code written using C++ STL template classes. Wil's manager Che asked Hal to help Wil do small details in a larger task, targeting items not worth Wil's time. But ironically, the two conversations with Hal took longer than Wil would have taken to code and test the non-essential task himself.
First Wil explained the problem to Hal, who knew nothing about the old source. The old code was a kind of combined hashmap and LRU list showing cache items ordered by recency of usage. It's a small collection of only 100 elements. It used STL before, which wasn't big enough to remove earlier for efficiency reasons. But now the STL library cannot be linked in the code.
This story skips Wil's detailed list of methods that must be supported without change in semantics. But the main idea is to put the same items into two different collections — one ordered by map key and ordered by LRU access. Wil tells Hal this is the same sort of data structure he's been writing for page caches since the 80's. Wil could replace it in an hour, but this i/o system is being retired in favor of Wil's new page cache. Hal's task is in old standby code.
"Do you want samples in C or C++?" Wil asked Hal.
"Which would you prefer?" Hal countered.
"You're in charge," Wil insisted, "So you should write the code however you feel most comfortable or more certain of good results."
"In that case," Hal suggested, "maybe C would be better. I am a bit more comfortable."
"No problem," Will assured, "Let me show you simple code in C to do hashmaps with tombstones. Let's use a mu_ code prefix as a namespace; it doesn't matter."
"This is an example hashmap entry associating a key with a value. Think of this as pair<mu_key*,int> in STL, but just using a simple struct."
"Okay," agreed Hal.
"The key can be anything you want," Wil continued. "Here let's assume mu_key is opaque — we don't know anything about it. All we know is an address. The e_val member is just a dummy since we need a value."
"Sure, of course," nodded Hal.
"So my example," explained Wil, "is only going to map unique addresses to integers. Assume the hashmap max capacity is 100 like in our use case."
"But not enough to do LRU list too," Hal observed. "Entry struct must be more."
"Yes," Wil confirmed. "When you actually code, you'll have a doubly-linked list element in the entry too. I won't show that — just the hashmap part."
"I understand completely," Hal assured.
"Here's the hashmap," Wil asserted. "It's a shared global array initialized to all zero, needing mutex I won't show — just getters and setters."
"You said single thread," Hal objected.
"Yes," Wil conceded. "In the main case. But we also want to use this map under threads."
"Why?" Hal insisted.
Wil replied patiently, "Because the LRU code you're replacing will only be used with memory mapping, and we'll only access disk that way using a thread pool."
"They said we won't use a disk," Hal countered.
"Well if I test that code," Wil enhanced, "it will be with a disk, so I can see if it does exactly the same thing as the old code. It's the only reason to reproduce the old code."
"I see," Hal stated, reserving further objection.
"Anyway," Wil went on, "I made size a prime well over max occupancy — over one third empty. It's a small unique array, so let's go big and keep collisions really sparse. Size should be prime with address-based keys."
"Does prime really matter?" asked Hal.
"Addresses of objects allocated in memory normally occur with some alignment," explained Wil. "So they'll cluster at address offsets unless we distribute them or make the mod prime for the hashmap."
"Distribute them?" wondered Hal.
"The keys," replied Wil. "Here they're addresses. Normally I run those through a pseudo random number generator. But it's only a hundred elements, so I don't want the random number code to add cost."
Wil sketched the next piece of code as Hal watched. "Nonzero add means caller is inserting," Wil glossed.
"This looks very complex," Hal objected.
"It's just a vector search starting in the middle," Wil soothed, "with wrap around to make it circular."
"I would worry I did it wrong," Hal complained.
"What can go wrong?" Wil asked. "Let's look at the code. The first entry is map and one entry past the last is end. Too much pointer arithmetic?"
"No, I am good with pointers," Hal asserted.
"Okay, then p is pseudo randomly chosen in the array," Wil continued. "And start remembers in case we loop — can't happen if we limit occupancy to 100."
"You always return entry p," Hal observed. "Why not return value?"
"Because find() is used by both get() and add() methods — the entry says where to put a new pair if the entry is not used."
"Caller checks for zero or tomb in key?" Hal asked.
"Yes, and since it was just touched, it's not a new cache line access," Wil explained.
"Looks linear," Hal suggested. "Why don't I search whole array? Much simpler, and speed cannot matter in 100 members."
"Most of the time," Wil countered, "this code will touch exactly one entry. That's not linear. It always hits at most one cache line. When you make entries bigger, you hit more than one cache line scanning arrays of 100."
"Time cannot possibly matter," Hal insisted.
"If you have a pool of dozens of threads," Wil countered, "linear search under mutex increases contention, even with N=100. It would break my rule."
"What rule?" Hal wondered.
"Constant time only under mutex," Wil replied.
"No one will ever know," Hal suggested.
"Ha, ha," Wil disagreed, "But they ask. Let's optimize linear operations, they say. There aren't any, I reply. Now I can't say that. That's why we code this way."
"I would prefer to do it my way," Hal noted.
"You're in charge," Wil agreed. "But if I test it later, I might change it to this. Let's look at code to remove."
Hal looked annoyed but watched Wil write.
"We assume input arg p was returned by find()", Wil explained. "So a caller uses find() first."
"This also looks complex," Hal confirms suspicion.
"Usually just one tombstone is removed," Wil claimed. "But this handles worst case collisions anyway."
"With disk i/o," Hal insisted. "speed of lookup cannot matter. I can scan array."
"The store might be memory only," Wil countered. "with a thread pool anyway. Or access might be from more than one process. That might use test-and-set mutex."
"The speed of nothing matters when disk is involved," Hal disagreed. "Linear is fine."
"The code must work for both: disk and memory-only," Wil informed Hal with a shrug. "Both will come up."
On the use of story format to convey ideas, see 03feb08 and background for brief explanations.
Zé edits footage of Wil's conversation with Hal, then later shows it to Ulf — selling an idea of using personal story material to build a new kind of website using fiction-based games mixed with socialization software.
"Over the years," Wil told Zé and Ulf later, "I've written many dozens of hashmap classes. Lately I write a new one-off hashmap every time I need one."
"Why so many?" Ulf puzzled. "Wouldn't it be simpler to use a generic hashmap class? What's wrong with STL's hashmap?"
Wil glanced at Zé. "Is he going to be like this all night?" Wil asked Zé, half pretending to exasperation.
"Humor Ulf this time," Zé suggested. Turning to Ulf, Zé noted, "Wil often takes less than an hour per hashmap, and he doesn't make mistakes. Each one is exactly suited to a minimum needed in new situations. Hashmap code is idiomatic — like you'd write a for-loop by rote."
"Yeah," Wil nodded. "Simple hashmaps are very simple. It's just vector iteration, but starting at a semi-random starting point within circular arrays: constant time for limited N members."
"Did you ever write generic hashmaps?" Ulf prompted.
"A few in the 90's," Wil acknowledged. "Then a few more in the early 2000's. The sort taking keys and values of any type, using closed and open hashing, both. Grow and rehash."
Zé chuckled, then clarified for Ulf. "By a 'few' Wil means dozens of hashmap classes based on the same general pattern, maybe sixty or seventy altogether, sometimes with more specific ones atop more general maps."
"But why?" Ulf persisted.
"To control how memory is used in each case," Wil explained. "I use off-the-shelf classes just like you when the result doesn't matter. But I've been writing scaling caches for a dozen years, which need to be threadsafe, and I can get a perfect fit when I tune it by hand. For example, I recently came up with a hashmap format that can't be corrupted, so I can share it between processes without locks. But that's a very special case. You can't use it for most hashmaps; just in this situation."
"And he can't talk about it, right Wil?" Zé elbowed Wil's ribs.
"I could," Wil disagreed, "but I can't explain what it's used for, since that would be saying too much."
"How do you avoid corruption?" Ulf wondered.
"Actually, I don't," Wil said smiling. "It just doesn't matter since a corrupt hashmap entry causes no harm — it contains no pointers, and any part that gets whacked causes it to harmlessly become meaningless. I can fill a gigabyte of RAM with it, and you can't make it crash the system by stepping on any of the bytes."
"Cool, I'm writing the patent application in my head as we speak," Ulf teased.
"Good luck with that," Wil rolled his eyes.
"What's wrong with STL?" asked Ulf.
"Nothing's wrong with STL," Wil shrugged.
"Stop being literal, Wil," pleaded Zé. "He means, why don't you use it? Specifically?"
Wil nodded, starting a gesture. "Usually to get more constant time operations. My data usually goes into more than one collection at once, but I still want constant time for each and every operation using less than a linear subset of all data."
Ulf prompted, "Otherwise you don't care?"
"Nope," Will agreed. "If STL gave me a bit more control over storage, letting me use intrinsic instead of extrinsic links, then finding an object in one place would find it in others too, without another lookup."
"STL hides memory management," Zé explained.
"So you can't control it?" Ulf asked.
"Not beyond replacing allocators," Wil observed. "So you can't easily use control over physical location to imply order one relationships."
"Order one means contant time," Zé noted. "That's O(1) in big Oh notation."
"I know that!" snapped Ulf. "I'm not an idiot. How does STL's hashmap measure up otherwise?"
"STL doesn't have a hashmap as standard," Zé interrupted. "Only in SGI's templates."
"That sucks!" blurted Ulf.
"STL's map is a tree," Wil agreed, "with speed distinctly inferior to hashmaps. But it sorts members."
"But trees are log time," argued Ulf, "so isn't that almost constant time? For small N?"
"Trees and lists touch a lot of different memory locations," explained Wil, "so the number of cache lines you hit is much higher in number."
"Cache lines," Ulf considered.
"Yeah, cache lines," Wil agreed. "Fewer is faster."
"What about standards?" Ulf whined.
"Stardard code APIs?" Wil qualified.
"Yeah," Ulf agreed. "If everyone uses the same library, the api is standard."
"I'm sure this occurred to you," Wil suggested, "but you can use a standard api with different libraries. I think the STL api is fine."
"So you use STL's api?" Ulf gawped.
"Sure, it's fine. And everyone already knows how to use it," Wil noted. "And I can replace STL with my code when I rewrite existing systems."
"But," Ulf wondered, "isn't it hard to replace the entire STL api? There's a lot."
"Yes," Wil granted, "but most folks use only a small part — I only replace that part."
"Does your code go faster?" Ulf challenged.
"Of course," Wil insisted. "But it's not hard to run direct comparisons by empirical test."
"Let the best man win," Ulf suggested.
"As often as possible," prayed Wil with steepled fingers. "My motto is argue less, test more."
"Arguing's more fun," Ulf objected.
"Don't make me slap you," Wil joked.
"Agent double-oh Ulf," Zé intoned, "licensed to argue. Nah, that's boring. Don't overdo it."
"What about cryptographic hashes?" Ulf blurted.
"Oh god," moaned Wil, "I hoped we were done."
"Ha, ha," laughed Ulf, "Never. I could get to liking the role of bad guy. How 'my doing?"
"You aren't being bad now —" Zé interposed, "just difficult. You need to work on craft and malice."
"The hash key used," Wil explained, "is independent of hashmap structure — almost. Weak or strong hashes normally won't change whether to use tombstones, for example. But collision rate matters."
"Yeah," Zé chimed in, "closed hashing — probing to resolve collisions — is a bad idea in the presence of hash clustering. Hashes must be good enough."
"Exactly," Wil agreed. "As long as you use a good collision-resistent hash — for data populations you expect — you'll be safe with closed hashing. But when you scale really big, keep maps a third empty."
"Cryptographic hashes are coool," crooned Ulf.
"Sure," Wil ceded. "But sometimes you only want a 32-bit hash so you get many more map entries in the same space. I often use crc32."
"And don't forget," Zé warned, "Cryptographic hashes are a bit slower than, say, crc32."
"Cache lines again?" anticipated Ulf.
"Yeah," Wil smiled. "The larger a data set touched, the slower cryptographic hashes usually go. Gotta watch how much CPU you consume."
"What if," Ulf narrowed his eyes, "it's really important to avoid generating the same hash from different content?"
"Duh," Zé replied pleasantly, "use a big cryptographic hash then. Depends on requirements."
Wil nodded. "Need to balance requirements."
"Tradeoffs," mumbled Ulf. All three nodded.
"You comment many lines of code," Ulf marveled.
"Yes," Wil nodded. "I like 'why' to appear next to 'how' of code."
"You always see 'what' code does," Zé agreed, "But coder intent is often missing without comments."
"I hate comments," groused Ulf. "They get out of sync with the code. So comments are evil."
"Look at my code," Wil instructed. "What do you see? Which comments can get out of sync?"
"Nearly all comments are on the same line as code they describe," guessed Ulf. "Maybe short is good."
"Uh huh," Wil agreed. "Would you change code on a line without fixing a comment on that line?"
"Must I be honest?" Ulf joked. "What about job security? Keeping code a mystery helps, right?"
"Job security is never an issue," Wil groaned. "I have way too much to do. It's a drag being the expert in everything. Let someone else learn how."
"Ever see closed hashing done wrong?" Ulf asked.
"Yes, at Netscape," Wil replied. "I was lecturing my boss on hashmap technique, and when I said you couldn't just delete old hash entries without rehashing or using tombstones, my boss said 'Oh, so that explains why those mail/news summary files are getting corrupt.'"
"Dang," Ulf commiserated. "So they fixed it?"
"No," Wil smiled. "That behavior was part of the db file format by then. Weird place to work."
"Tell me some Netscape dirt," Ulf urged.
"No," replied Wil shortly.
"Wear this button," Zé said, handing one to Ulf.
"'Strange is okay'," read Ulf. "What's it mean?"
"My motto 'argue less' is shorter," bragged Wil.
"Where we're going," explained Zé, "you'll be beaten up if you don't wear this button."
"You're kidding, right?" pleaded Ulf.
"Just til they get to know you," continued Zé. "They're intolerant of fiction newbies."
"Noob," snickered Wil.
"You know I'll get even," warned Ulf.
tombstones « Þ
