4 ms·

Two things to keep in mind: Pre-internet, it was quite easy to be skilled and knowledgeable and yet never have been exposed to something another community somew

by jerf 2y ago

Two things to keep in mind: Pre-internet, it was quite easy to be skilled and knowledgeable and yet never have been exposed to something another community somewhere would consider basic, or for it to take many many years to percolate across. I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. Second, while the programming world fancies itself a very fast mover, it really isn't, and it especially wasn't back then. 20 years isn't necessarily as long as you would think in 2024. We're still trying to convince people in 2024 that you really don't need a language that will happily index outside of arrays, and how long has that been a staple in existing languages? (You may think that's silly, but we've had that fight on HN, yes, yea verily, this very year. Granted, this is winding down, but it's still a live argument.) There's a lot of things that showed up in some language in the 1960s or 1970s and wasn't widely adopted for another few decades. (Though I suspect one problem with Lisp is that back in the day, its performance was pretty awful relative to the other things of the day. It was not always the best advertisement for its features. A bit too ahead of its time sometimes.)

Zambyte 2y ago
I totally get the first point, but this comment from Brian was made when the internet had been available for many, many years. It seems more like it felt newish at the time, and that is how he has seen it since then. I guess that's more why I find it to be an interesting comment. Regarding the second point, when I hear the term "associative arrays" or "associative lists" I think of them in a pretty high level of abstraction. Like really: a C struct is an association abstraction. A simple array of structs is not often considered an "associative array", but it can easily be used for the same things. Maybe it would be more accurate to say that the way they were using associative arrays way newish, rather than the construct itself.
vram22 2y ago
>I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. That's a little surprising, considering that the classic first book about C, K&R was first published in 1978 and again in 1988, the first and second edition, respectively. One of the editions, maybe the first, had a simple hash table implementation, that just summed up the ASCII values of the characters in the given string, modulo some value, and used that as the key for the string being hashed. . https://en.m.wikipedia.org/wiki/The_C_Programming_Language https://en.m.wikipedia.org/wiki/The_C_Programming_Language
xarope 2y ago
I remember being taught about associative caches in CPU architecture, and later on programming the same in C. So I'm not sure about the 90's and hash tables being "exotic". My first real use of hashes was in perl4; with perl5 released in 1996 (https://dev.perl.org/perl5/news/ https://dev.perl.org/perl5/news/), surely it meant people were also well aware of the usefulness of hash arrays even back then.
- cancerhacker 2y ago
  It was a common practical interview question in 1996 to ask a candidate to implement a hash table in C.
  - satiated_grue 2y ago
    I recall implementing hash tables in COBOL on a Univac. Not even kidding a little.
kragen 2y ago
the picture you're painting here is absurdly far from reality — kernighan definitely did not think hash tables were 'a bit exotic' in 01978 — hash tables (or sometimes other associative retrieval structures) were standard fare in computer science degree programs and were a standard feature of compilers, assemblers, and linkers, of which kernighan had written several at that point; associative retrieval structures are also fundamental to databases and filesystems. in 01979, 7th edition unix (in which kernighan published awk) barely had date formatting but included an on-disk hash table library called 'dbm' hash tables are the exclusive topic of pp. 506–549 of knuth's taocp volume 3, a standard textbook which came out in 01973. after recommending you some hash functions, on p. 512 (525/739) knuth recommends you check out a survey of hash functions published in cacm by lum, yuen, and dodd in 01971, and he cites papers on hashing in cacm as early as 01959 and in an ibm journal as early as 01957. in the 'history' section (pp. 540–542 (553–555/739)) he traces it back to an internal ibm report by luhn in 01953, and its first report in the open literature to a paper by dumey in 01956. most of the rest of the 739-page book is about how to implement associative arrays of various kinds, although some parts instead concern the string search problem, and the first half is about sorting, and a sorted table can be used for purposes other than associative retrieval knuth also mentions a 'very influential survey' of hashing published in cacm in 01968 by robert morris, kernighan's coworker at bell labs, and one of the very first users of unix and a major contributor to it there are several papers about hashing every year in cacm throughout the 01970s, as well as alternative associative-array structures such as tries, sorted arrays and binary search trees. in march 01975 we have https://cacm.acm.org/research/the-algorithm-sequential-access-method/ https://cacm.acm.org/research/the-algorithm-sequential-acces..., in april 01975 we have https://cacm.acm.org/research/the-quadratic-hash-method-when-the-table-size-is-not-a-prime-number/ https://cacm.acm.org/research/the-quadratic-hash-method-when..., in may 01975 we have https://cacm.acm.org/research/analysis-and-performance-of-inverted-data-base-structures/ https://cacm.acm.org/research/analysis-and-performance-of-in..., in july 01975 we have https://cacm.acm.org/research/a-note-on-hash-linking/ https://cacm.acm.org/research/a-note-on-hash-linking/, in september 01975 we have https://cacm.acm.org/research/multidimensional-binary-search-trees-used-for-associative-searching/ https://cacm.acm.org/research/multidimensional-binary-search..., in october 01975 we have https://cacm.acm.org/research/optimizing-the-performance-of-a-relational-algebra-database-interface/ https://cacm.acm.org/research/optimizing-the-performance-of-... and https://cacm.acm.org/research/merging-with-parallel-processors/ https://cacm.acm.org/research/merging-with-parallel-processo..., in january 01976 we have https://cacm.acm.org/research/performance-of-height-balanced-trees/ https://cacm.acm.org/research/performance-of-height-balanced..., in february 01976 we have https://cacm.acm.org/research/on-self-organizing-sequential-search-heuristics/ https://cacm.acm.org/research/on-self-organizing-sequential-... and https://cacm.acm.org/research/a-stochastic-evaluation-model-for-database-organizations-in-data-retrieval-systems/ https://cacm.acm.org/research/a-stochastic-evaluation-model-..., in june 01976 we have https://cacm.acm.org/research/a-practitioners-guide-to-addressing-algorithms/ https://cacm.acm.org/research/a-practitioners-guide-to-addre... (which is about hashing despite the name), in july 01976 we have https://cacm.acm.org/research/compressed-tries/ https://cacm.acm.org/research/compressed-tries/, and in august 01976 we have https://cacm.acm.org/research/an-insertion-technique-for-one-sided-height-balanced-trees/ https://cacm.acm.org/research/an-insertion-technique-for-one.... you could not read cacm in the 01960s and 01970s without frequently coming across hashing, as well as other associative-array structures. but perhaps kernighan hadn't read cacm? on the contrary, he and his colleagues regularly published in it; he published in cacm once in 01972, once in 01973, and once in 01975, and his colleagues such as stephen johnson, mike lesk, al aho (his coauthor on awk), and, as i said above, robert morris, published there regularly as well in the practice of programming, kernighan and pike claim that almost all of the time, the only data structures you need are arrays, linked lists, trees, and hash tables (though they wrote this in 01999) what kernighan is talking about here is including them as a basic language construct, a design choice his 01978 tech report on awk likens to that of snobol4, which was a well-known language but not a mainstream one. in the context of the above cacm articles, you can perhaps see that the daring choice was to offer a single 'good enough' hash table implementation rather than one optimized for a given purpose—and to use it even in place of conventional arrays — kernighan was not isolated like you were — kernighan was at bell labs, which was probably the most connected place in the software world at the time when awk was released in 01979 the internet was already ten years old, and at&t (the parent company of bell labs) had installed all its long-distance links in 01976 they'd also developed their own 'internet' called uucp, which at the time of awk's release was interconnecting 80 different unix sites, interchanging software updates on a daily basis, over 300-baud and 1200-baud modems. they were also in contact with ken thompson's alma mater berkeley; thompson took a sabbatical year to teach there in 01975. berkeley got a darpa contract to add tcp/ip support to the bell labs operating system 'unix', which would become the majority of the internet during the 01980s; berkeley participated actively in the uucp network bell labs was also working on the so-called 'advanced communication system', its own misconceived version of the internet, where data would be routed using phone numbers, because data communications had become the fastest-growing source of call traffic. (colin berkshire has written a fantastic overview of this forgotten history.)

by jerf 2y ago

Zambyte 2y ago

I totally get the first point, but this comment from Brian was made when the internet had been available for many, many years. It seems more like it felt newish at the time, and that is how he has seen it since then. I guess that's more why I find it to be an interesting comment. Regarding the second point, when I hear the term "associative arrays" or "associative lists" I think of them in a pretty high level of abstraction. Like really: a C struct is an association abstraction. A simple array of structs is not often considered an "associative array", but it can easily be used for the same things. Maybe it would be more accurate to say that the way they were using associative arrays way newish, rather than the construct itself.

vram22 2y ago

>I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. That's a little surprising, considering that the classic first book about C, K&R was first published in 1978 and again in 1988, the first and second edition, respectively. One of the editions, maybe the first, had a simple hash table implementation, that just summed up the ASCII values of the characters in the given string, modulo some value, and used that as the key for the string being hashed. . https://en.m.wikipedia.org/wiki/The_C_Programming_Language https://en.m.wikipedia.org/wiki/The_C_Programming_Language

xarope 2y ago

I remember being taught about associative caches in CPU architecture, and later on programming the same in C. So I'm not sure about the 90's and hash tables being "exotic". My first real use of hashes was in perl4; with perl5 released in 1996 (https://dev.perl.org/perl5/news/ https://dev.perl.org/perl5/news/), surely it meant people were also well aware of the usefulness of hash arrays even back then.

cancerhacker 2y ago
It was a common practical interview question in 1996 to ask a candidate to implement a hash table in C.
- satiated_grue 2y ago
  I recall implementing hash tables in COBOL on a Univac. Not even kidding a little.

kragen 2y ago

the picture you're painting here is absurdly far from reality — kernighan definitely did not think hash tables were 'a bit exotic' in 01978 — hash tables (or sometimes other associative retrieval structures) were standard fare in computer science degree programs and were a standard feature of compilers, assemblers, and linkers, of which kernighan had written several at that point; associative retrieval structures are also fundamental to databases and filesystems. in 01979, 7th edition unix (in which kernighan published awk) barely had date formatting but included an on-disk hash table library called 'dbm' hash tables are the exclusive topic of pp. 506–549 of knuth's taocp volume 3, a standard textbook which came out in 01973. after recommending you some hash functions, on p. 512 (525/739) knuth recommends you check out a survey of hash functions published in cacm by lum, yuen, and dodd in 01971, and he cites papers on hashing in cacm as early as 01959 and in an ibm journal as early as 01957. in the 'history' section (pp. 540–542 (553–555/739)) he traces it back to an internal ibm report by luhn in 01953, and its first report in the open literature to a paper by dumey in 01956. most of the rest of the 739-page book is about how to implement associative arrays of various kinds, although some parts instead concern the string search problem, and the first half is about sorting, and a sorted table can be used for purposes other than associative retrieval knuth also mentions a 'very influential survey' of hashing published in cacm in 01968 by robert morris, kernighan's coworker at bell labs, and one of the very first users of unix and a major contributor to it there are several papers about hashing every year in cacm throughout the 01970s, as well as alternative associative-array structures such as tries, sorted arrays and binary search trees. in march 01975 we have https://cacm.acm.org/research/the-algorithm-sequential-access-method/ https://cacm.acm.org/research/the-algorithm-sequential-acces..., in april 01975 we have https://cacm.acm.org/research/the-quadratic-hash-method-when-the-table-size-is-not-a-prime-number/ https://cacm.acm.org/research/the-quadratic-hash-method-when..., in may 01975 we have https://cacm.acm.org/research/analysis-and-performance-of-inverted-data-base-structures/ https://cacm.acm.org/research/analysis-and-performance-of-in..., in july 01975 we have https://cacm.acm.org/research/a-note-on-hash-linking/ https://cacm.acm.org/research/a-note-on-hash-linking/, in september 01975 we have https://cacm.acm.org/research/multidimensional-binary-search-trees-used-for-associative-searching/ https://cacm.acm.org/research/multidimensional-binary-search..., in october 01975 we have https://cacm.acm.org/research/optimizing-the-performance-of-a-relational-algebra-database-interface/ https://cacm.acm.org/research/optimizing-the-performance-of-... and https://cacm.acm.org/research/merging-with-parallel-processors/ https://cacm.acm.org/research/merging-with-parallel-processo..., in january 01976 we have https://cacm.acm.org/research/performance-of-height-balanced-trees/ https://cacm.acm.org/research/performance-of-height-balanced..., in february 01976 we have https://cacm.acm.org/research/on-self-organizing-sequential-search-heuristics/ https://cacm.acm.org/research/on-self-organizing-sequential-... and https://cacm.acm.org/research/a-stochastic-evaluation-model-for-database-organizations-in-data-retrieval-systems/ https://cacm.acm.org/research/a-stochastic-evaluation-model-..., in june 01976 we have https://cacm.acm.org/research/a-practitioners-guide-to-addressing-algorithms/ https://cacm.acm.org/research/a-practitioners-guide-to-addre... (which is about hashing despite the name), in july 01976 we have https://cacm.acm.org/research/compressed-tries/ https://cacm.acm.org/research/compressed-tries/, and in august 01976 we have https://cacm.acm.org/research/an-insertion-technique-for-one-sided-height-balanced-trees/ https://cacm.acm.org/research/an-insertion-technique-for-one.... you could not read cacm in the 01960s and 01970s without frequently coming across hashing, as well as other associative-array structures. but perhaps kernighan hadn't read cacm? on the contrary, he and his colleagues regularly published in it; he published in cacm once in 01972, once in 01973, and once in 01975, and his colleagues such as stephen johnson, mike lesk, al aho (his coauthor on awk), and, as i said above, robert morris, published there regularly as well in the practice of programming, kernighan and pike claim that almost all of the time, the only data structures you need are arrays, linked lists, trees, and hash tables (though they wrote this in 01999) what kernighan is talking about here is including them as a basic language construct, a design choice his 01978 tech report on awk likens to that of snobol4, which was a well-known language but not a mainstream one. in the context of the above cacm articles, you can perhaps see that the daring choice was to offer a single 'good enough' hash table implementation rather than one optimized for a given purpose—and to use it even in place of conventional arrays — kernighan was not isolated like you were — kernighan was at bell labs, which was probably the most connected place in the software world at the time when awk was released in 01979 the internet was already ten years old, and at&t (the parent company of bell labs) had installed all its long-distance links in 01976 they'd also developed their own 'internet' called uucp, which at the time of awk's release was interconnecting 80 different unix sites, interchanging software updates on a daily basis, over 300-baud and 1200-baud modems. they were also in contact with ken thompson's alma mater berkeley; thompson took a sabbatical year to teach there in 01975. berkeley got a darpa contract to add tcp/ip support to the bell labs operating system 'unix', which would become the majority of the internet during the 01980s; berkeley participated actively in the uucp network bell labs was also working on the so-called 'advanced communication system', its own misconceived version of the internet, where data would be routed using phone numbers, because data communications had become the fastest-growing source of call traffic. (colin berkshire has written a fantastic overview of this forgotten history.)