8 ms·

Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

266 points by saadalem 7y ago

znpy 7y ago
I'd sort the input as it arrives, using heap sort. The thing is, you could just not worry about the stream, as it is TCP/IP based. The core idea is to read a number from the stream, append to the array that makes up the heap, and run heap sort. The only important thing is to keep the tcp/ip connection alive. If sorting takes too much, tcp will take care of sending the last sent number again. This might not be super efficient though. This could also be done in batches (4kb? 8kb?) -- we don't know about network speed or latencies, so we might work on that.
- gregschlom 7y ago
  You can't because there's not enough RAM to hold all the numbers. So you'd be sorting the input as it arrives, yes, and then at some point you'd run out of RAM and have to stop processing new numbers.
  - deleted 7y ago
    [deleted]
  - vbezhenar 7y ago
    There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using 27 bits per number won't hold them all indeed. But if you would store them ordered and store difference rather than number using variable bit encoding, it would take less space. Just simple math: imagine that you have to store numbers 0, 100, 200, ..., 99 999 900 as a worst case scenario. As you're going to store the differences, you'll need to store "0" and then "100" 999999 times. If you would be able to represent "100" with 8 bits, you'll be able to keep your data inside 1 MiB limit. One simple encoding: 1xxxxxx for 7 bits; 01xxxxxxxx for 8 bits; 001xxxxxxxxx for 9 bits, etc. It should be enough for this task, although you could invent better encodings.
    - ecpottinger 7y ago
      That my idea too. It is very unlikely that the numbers are spread apart enough that you can't store the deltas in compact forms. Example starting your base as zero if the first number 100 you can store that in 1 byte, use the high bit to flag a larger number so if the next number is say 10000 you can store it in two bytes. But let's say the next number is 3000, you need to update the first delta, insert the new number and continue on. You probably can store most numbers that way.
MrStonedOne 7y ago
A more practical version of that same solution would be to use some serverless endpoint to do the sorting (or even just the storing).
- hyperman1 7y ago
  OK, since we're now in evil question territory: How long should the wire to the router be to store everything? Assuming no buffer in the router and gygabit ethernet.
gregschlom 7y ago
This is basically an ICMP-based version of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
- throwaway777555 7y ago
  They're both similar and very clever, but they do operate differently. Sleep sort works by setting up a delay and callback based on the values that you are sorting, so timing is crucial. The solution in this topic is using the network as a queue to store values and is constantly throwing them back, only pulling them into the sorted stack when they reach the max threshold. Once an item is pulled down, its value is recorded and isn't echoed out again. The process is repeated until the list is complete. This works without regard to timing.
- perl4ever 7y ago
  "Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests" This sounds to me like... https://en.wikipedia.org/wiki/Delay_line_memory https://en.wikipedia.org/wiki/Delay_line_memory
  - jfitzsimons 7y ago
    It's complicated by the fact that ICMP packets do not necessarily arrive in order.
pixelmonkey 7y ago
This question is not the same as -- but has a similar feel to -- the first programming problem in the classic book "Programming Pearls"[1]. You can read it on O'Reilly Safari these days[2]. Even if you don't read the book, that first chapter, "Cracking the Oyster", is worth a read. It's a fun problem. [1]: https://amzn.to/2vWkZ0D https://amzn.to/2vWkZ0D [2]: https://learning.oreilly.com/library/view/programming-pearls-second/9780134498058/ch01.html https://learning.oreilly.com/library/view/programming-pearls...
taberiand 7y ago
The accepted solution is some wizardry that works because 1M (just) fits into 1MB... I wonder if in the intervening years 1M hasn't become 2M or more? I'm not really smart enough to come up with such a solution, I'd probably just try and find a way to plug something in between the input or output Ethernet port that has a bit more memory.
- YetAnotherNick 7y ago
  1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits)
  - dan-robertson 7y ago
    I think your calculation for ordered lists is just wrong. I think the right answer should be about 3.17MB, not 3.5.
    - YetAnotherNick 7y ago
      Someone wrote 3.5MB, didn't bother to double check but the formula is correct.
csunbird 7y ago
just do an external merge sort https://en.wikipedia.org/wiki/External_sorting#External_merge_sort https://en.wikipedia.org/wiki/External_sorting#External_merg...
- oldgradstudent 7y ago
  That assumes external storage, which is not given in the problem statement.
raverbashing 7y ago
I think you can assume 8-digit numbers can be stored in 27 bits The relationship between cardinality of the codomain and image of the numbers is approximately 100 I would try to convert incoming numbers into pairs/tuples of N + differences (which can be done using less bits)
Palomides 7y ago
I wonder if the author was familiar with https://en.wikipedia.org/wiki/Delay_line_memory https://en.wikipedia.org/wiki/Delay_line_memory
the_arun 7y ago
This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.
- ohlookabird 7y ago
  But there are for instance modern embedded systems which might be very resource constrained and knowledge like this would be useful there.
- cfallin 7y ago
  Compact / succinct data structures and clever algorithms are still very important when data gets large enough -- consider e.g. a database running complex queries, where a good encoding makes the difference between staying in memory and going to disk. Basically the machines became larger but so have the problems to solve.
  - Dylan16807 7y ago
    Yes but this is far beyond compact, it's squeezing in so close to the edge of what fits that the performance inevitably drops off a cliff.
raphlinus 7y ago
I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 https://news.ycombinator.com/item?id=4679756), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific encoding I used for the sorted list: A '0' bit followed by 12 bits of payload generates a number which is those 12 bits added to a global state counter. A '1' bit increments the global state counter by 2^12. It's easy to work out the memory requirements (it's constant for all sorted lists of the same length): 2^20 bits for the '1' bits (to reach a maximum value of 2^32) plus 10^6 * 13 bits for the integers. This is exactly 1,756,072 bytes, which leaves plenty of extra space. ETA: unfortunately a simple adaptation of this technique doesn't quite work for this problem; the optimum payload size for 1e6 integers up to 1e8 is 6 bits, but even with that the representation takes 1046kiB, and the budget is 1024kiB.
- bogomipz 7y ago
  >"I'm a fan of the actual (in-RAM, no tricks) problem and its variants." This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.
  - raphlinus 7y ago
    I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.
    - mikepurvis 7y ago
      The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.
tetris11 7y ago
Hang on, he decrements VALUE only by 1 during the sorting phase, which assumes that the 1M 8 digit numbers are consecutive, which we know they might not he because he said there could be duplicates....
- throwaway744678 7y ago
  After decreasing VALUE by 1, you should run T (T >> 10000000) times. If VALUE is not found in your stream, it is not transmitted. Similarly, you should always run T times, to account for all duplicates (you can't just 'break' when finding VALUE)
tomaszs 7y ago
Its easy. 1kk numbers fit almost whole 1MB. So most of the numbers from the range will be there if we assume normal distribution. So we need to compress the data first in a way we can still count it. So we take a sinus function and mark multipliers where a number does not fit sinus. So we spare 0,5MB of RAM at least. Then we iterate the range, multiply sinus and output sorted numbers. Rest of the RAM can be used for example for bitcoin mining
- saagarjha 7y ago
  Bitcoin mining hinges on computing hashes, though.
  - tomaszs 7y ago
    It was a figure of speech. Still my way is valid
jayd16 7y ago
The accepted answer seems prone to losing data on dropped packets, no? A similar (but I think safer) approach might be to read ahead all the packets to determine what values you can begin to send. Then you could request retransmission. This requires the sender to play nice and buffer all the data fore you but that seems more realistic than assuming the router will do so.
- ADefenestrator 7y ago
  "prone to" is putting it mildly. ICMP echo requests tend to be processed by the often relatively anemic control plane CPU rather than ASICS and are at the bottom of the heap in terms priority. If you send a router 1MB of ICMP echo requests, it's virtually guaranteed to drop some or even most of them.
deleted 7y ago
[deleted]
perl4ever 7y ago
I'm vaguely thinking set a TCP sequence number according to each number you want to sort, then use the out of order capability of TCP/IP to do it for you...
- dan-robertson 7y ago
  But you’d need to either send your million packets somewhere with enough memory (if you can do that, why not just send the numbers to the box with sufficient memory in the first place), and you’d need to be able to look at each input number and decide what sequence number to assign to the outgoing packet (you can’t use the number itself as numbers may be duplicated but seqnums may not, and you can’t have enough memory to know if it’s a duplicate without solving the problem. Also you won’t be able to have missing seqnums in the set of all packets you send, and wherever you send the packets won’t put up with you sending a million packets (let alone the 2^27 or so you might need if you sent every 8-digit number) out of order.
fnord77 7y ago
Has anyone implemented this?
known 7y ago
Can't we do it in AWK https://blog.jpalardy.com/posts/alternative-to-sort-uniq-c/ https://blog.jpalardy.com/posts/alternative-to-sort-uniq-c/
nikeee 7y ago
Reminds me of pingfs: https://github.com/yarrick/pingfs https://github.com/yarrick/pingfs
- jfitzsimons 7y ago
  Oh, cool! In my defence, I can only say that I believe my answer predates this.
jankotek 7y ago
Simple with External Merge Sort https://en.m.wikipedia.org/wiki/External_sorting#External_merge_sort https://en.m.wikipedia.org/wiki/External_sorting#External_me...
- Traster 7y ago
  No it isn't, because the problem specifies that you have 1 MB of RAM and no other local storage. You don't have a disk to write back out to.
jfitzsimons 7y ago
I have only ever answered one question on SO, and this was it. I used to be pretty active on some of the other sites (cstheory and the old theoretical physics stack exchange) but this answer got enough attention that I immediately vowed not to post to SO again, since it could only damage my track record there.
- ignoramous 7y ago
  Thanks. Since you're here, I'd like to take the liberty of asking: 1. What was the inspiration behind that answer? 2. Have you stumbled upon other such quirky techniques elsewhere that rival yours? 3. Any interesting anectode about someone who put your solution in production / research paper / homework and later reached out to you for help?
  - jfitzsimons 7y ago
    There have been a few edits to my answer since I originally posted it. The original version had a bit at the top about it being against the spirit of the question but intended to amuse. It's not a practical solution at all. Re 1: I'm not sure there was any particular inspiration. I've worked on quantum computing since 2004, so I guess I spend a lot of time thinking how to make computers in weird ways. Plus I spent college working at a number of ISPs doing tech support, so I used to be reasonably up on networks. Re 2: Yep. In my field there is this idea of quantum sneaker-net. This is far more useful than my answer and potentially solves a major problem in the field I work in, but is also totally off the wall. The basic idea is that you can make an extremely high speed low latency network for quantum communication by shipping giant refridgerators around the world on ships (using a quantum effect and the existing [non-quantum] internet). The paper is here: https://www.nature.com/articles/srep36163 https://www.nature.com/articles/srep36163 Re 3: Somebody here pointed out pingfs which seems to take the idea to a whole new extreme, but reading the website it seems like it was already being worked on in 2011. I doubt anyone implemented my answer in any way. It was somewhat intentionally impractical.
gumby 7y ago
This solution is how RAM was implemented on some early computers, with acoustical memory in mercury delay lines. Crazy! I saw one at the computer history museum and realized that it weighed tons!

266 points by saadalem 7y ago

znpy 7y ago

I'd sort the input as it arrives, using heap sort. The thing is, you could just not worry about the stream, as it is TCP/IP based. The core idea is to read a number from the stream, append to the array that makes up the heap, and run heap sort. The only important thing is to keep the tcp/ip connection alive. If sorting takes too much, tcp will take care of sending the last sent number again. This might not be super efficient though. This could also be done in batches (4kb? 8kb?) -- we don't know about network speed or latencies, so we might work on that.

gregschlom 7y ago
You can't because there's not enough RAM to hold all the numbers. So you'd be sorting the input as it arrives, yes, and then at some point you'd run out of RAM and have to stop processing new numbers.
- deleted 7y ago
  [deleted]
- vbezhenar 7y ago
  There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using 27 bits per number won't hold them all indeed. But if you would store them ordered and store difference rather than number using variable bit encoding, it would take less space. Just simple math: imagine that you have to store numbers 0, 100, 200, ..., 99 999 900 as a worst case scenario. As you're going to store the differences, you'll need to store "0" and then "100" 999999 times. If you would be able to represent "100" with 8 bits, you'll be able to keep your data inside 1 MiB limit. One simple encoding: 1xxxxxx for 7 bits; 01xxxxxxxx for 8 bits; 001xxxxxxxxx for 9 bits, etc. It should be enough for this task, although you could invent better encodings.
  - ecpottinger 7y ago
    That my idea too. It is very unlikely that the numbers are spread apart enough that you can't store the deltas in compact forms. Example starting your base as zero if the first number 100 you can store that in 1 byte, use the high bit to flag a larger number so if the next number is say 10000 you can store it in two bytes. But let's say the next number is 3000, you need to update the first delta, insert the new number and continue on. You probably can store most numbers that way.

MrStonedOne 7y ago

A more practical version of that same solution would be to use some serverless endpoint to do the sorting (or even just the storing).

hyperman1 7y ago
OK, since we're now in evil question territory: How long should the wire to the router be to store everything? Assuming no buffer in the router and gygabit ethernet.

gregschlom 7y ago

This is basically an ICMP-based version of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

throwaway777555 7y ago
They're both similar and very clever, but they do operate differently. Sleep sort works by setting up a delay and callback based on the values that you are sorting, so timing is crucial. The solution in this topic is using the network as a queue to store values and is constantly throwing them back, only pulling them into the sorted stack when they reach the max threshold. Once an item is pulled down, its value is recorded and isn't echoed out again. The process is repeated until the list is complete. This works without regard to timing.
perl4ever 7y ago
"Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests" This sounds to me like... https://en.wikipedia.org/wiki/Delay_line_memory https://en.wikipedia.org/wiki/Delay_line_memory
- jfitzsimons 7y ago
  It's complicated by the fact that ICMP packets do not necessarily arrive in order.

pixelmonkey 7y ago

This question is not the same as -- but has a similar feel to -- the first programming problem in the classic book "Programming Pearls"[1]. You can read it on O'Reilly Safari these days[2]. Even if you don't read the book, that first chapter, "Cracking the Oyster", is worth a read. It's a fun problem. [1]: https://amzn.to/2vWkZ0D https://amzn.to/2vWkZ0D [2]: https://learning.oreilly.com/library/view/programming-pearls-second/9780134498058/ch01.html https://learning.oreilly.com/library/view/programming-pearls...

taberiand 7y ago

The accepted solution is some wizardry that works because 1M (just) fits into 1MB... I wonder if in the intervening years 1M hasn't become 2M or more? I'm not really smart enough to come up with such a solution, I'd probably just try and find a way to plug something in between the input or output Ethernet port that has a bit more memory.

YetAnotherNick 7y ago
1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits)
- dan-robertson 7y ago
  I think your calculation for ordered lists is just wrong. I think the right answer should be about 3.17MB, not 3.5.
  - YetAnotherNick 7y ago
    Someone wrote 3.5MB, didn't bother to double check but the formula is correct.

csunbird 7y ago

just do an external merge sort https://en.wikipedia.org/wiki/External_sorting#External_merge_sort https://en.wikipedia.org/wiki/External_sorting#External_merg...

oldgradstudent 7y ago
That assumes external storage, which is not given in the problem statement.

raverbashing 7y ago

I think you can assume 8-digit numbers can be stored in 27 bits The relationship between cardinality of the codomain and image of the numbers is approximately 100 I would try to convert incoming numbers into pairs/tuples of N + differences (which can be done using less bits)

Palomides 7y ago

I wonder if the author was familiar with https://en.wikipedia.org/wiki/Delay_line_memory https://en.wikipedia.org/wiki/Delay_line_memory

the_arun 7y ago

This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.

ohlookabird 7y ago
But there are for instance modern embedded systems which might be very resource constrained and knowledge like this would be useful there.
cfallin 7y ago
Compact / succinct data structures and clever algorithms are still very important when data gets large enough -- consider e.g. a database running complex queries, where a good encoding makes the difference between staying in memory and going to disk. Basically the machines became larger but so have the problems to solve.
- Dylan16807 7y ago
  Yes but this is far beyond compact, it's squeezing in so close to the edge of what fits that the performance inevitably drops off a cliff.

raphlinus 7y ago

I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 https://news.ycombinator.com/item?id=4679756), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific encoding I used for the sorted list: A '0' bit followed by 12 bits of payload generates a number which is those 12 bits added to a global state counter. A '1' bit increments the global state counter by 2^12. It's easy to work out the memory requirements (it's constant for all sorted lists of the same length): 2^20 bits for the '1' bits (to reach a maximum value of 2^32) plus 10^6 * 13 bits for the integers. This is exactly 1,756,072 bytes, which leaves plenty of extra space. ETA: unfortunately a simple adaptation of this technique doesn't quite work for this problem; the optimum payload size for 1e6 integers up to 1e8 is 6 bits, but even with that the representation takes 1046kiB, and the budget is 1024kiB.

bogomipz 7y ago
>"I'm a fan of the actual (in-RAM, no tricks) problem and its variants." This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.
- raphlinus 7y ago
  I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.
  - mikepurvis 7y ago
    The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.

tetris11 7y ago

Hang on, he decrements VALUE only by 1 during the sorting phase, which assumes that the 1M 8 digit numbers are consecutive, which we know they might not he because he said there could be duplicates....

throwaway744678 7y ago
After decreasing VALUE by 1, you should run T (T >> 10000000) times. If VALUE is not found in your stream, it is not transmitted. Similarly, you should always run T times, to account for all duplicates (you can't just 'break' when finding VALUE)

tomaszs 7y ago

Its easy. 1kk numbers fit almost whole 1MB. So most of the numbers from the range will be there if we assume normal distribution. So we need to compress the data first in a way we can still count it. So we take a sinus function and mark multipliers where a number does not fit sinus. So we spare 0,5MB of RAM at least. Then we iterate the range, multiply sinus and output sorted numbers. Rest of the RAM can be used for example for bitcoin mining

saagarjha 7y ago
Bitcoin mining hinges on computing hashes, though.
- tomaszs 7y ago
  It was a figure of speech. Still my way is valid

jayd16 7y ago

The accepted answer seems prone to losing data on dropped packets, no? A similar (but I think safer) approach might be to read ahead all the packets to determine what values you can begin to send. Then you could request retransmission. This requires the sender to play nice and buffer all the data fore you but that seems more realistic than assuming the router will do so.

ADefenestrator 7y ago
"prone to" is putting it mildly. ICMP echo requests tend to be processed by the often relatively anemic control plane CPU rather than ASICS and are at the bottom of the heap in terms priority. If you send a router 1MB of ICMP echo requests, it's virtually guaranteed to drop some or even most of them.

deleted 7y ago

[deleted]

perl4ever 7y ago

I'm vaguely thinking set a TCP sequence number according to each number you want to sort, then use the out of order capability of TCP/IP to do it for you...

dan-robertson 7y ago
But you’d need to either send your million packets somewhere with enough memory (if you can do that, why not just send the numbers to the box with sufficient memory in the first place), and you’d need to be able to look at each input number and decide what sequence number to assign to the outgoing packet (you can’t use the number itself as numbers may be duplicated but seqnums may not, and you can’t have enough memory to know if it’s a duplicate without solving the problem. Also you won’t be able to have missing seqnums in the set of all packets you send, and wherever you send the packets won’t put up with you sending a million packets (let alone the 2^27 or so you might need if you sent every 8-digit number) out of order.

fnord77 7y ago

Has anyone implemented this?

known 7y ago

Can't we do it in AWK https://blog.jpalardy.com/posts/alternative-to-sort-uniq-c/ https://blog.jpalardy.com/posts/alternative-to-sort-uniq-c/

nikeee 7y ago

Reminds me of pingfs: https://github.com/yarrick/pingfs https://github.com/yarrick/pingfs

jfitzsimons 7y ago
Oh, cool! In my defence, I can only say that I believe my answer predates this.

jankotek 7y ago

Simple with External Merge Sort https://en.m.wikipedia.org/wiki/External_sorting#External_merge_sort https://en.m.wikipedia.org/wiki/External_sorting#External_me...

Traster 7y ago
No it isn't, because the problem specifies that you have 1 MB of RAM and no other local storage. You don't have a disk to write back out to.

jfitzsimons 7y ago

I have only ever answered one question on SO, and this was it. I used to be pretty active on some of the other sites (cstheory and the old theoretical physics stack exchange) but this answer got enough attention that I immediately vowed not to post to SO again, since it could only damage my track record there.

ignoramous 7y ago
Thanks. Since you're here, I'd like to take the liberty of asking: 1. What was the inspiration behind that answer? 2. Have you stumbled upon other such quirky techniques elsewhere that rival yours? 3. Any interesting anectode about someone who put your solution in production / research paper / homework and later reached out to you for help?
- jfitzsimons 7y ago
  There have been a few edits to my answer since I originally posted it. The original version had a bit at the top about it being against the spirit of the question but intended to amuse. It's not a practical solution at all. Re 1: I'm not sure there was any particular inspiration. I've worked on quantum computing since 2004, so I guess I spend a lot of time thinking how to make computers in weird ways. Plus I spent college working at a number of ISPs doing tech support, so I used to be reasonably up on networks. Re 2: Yep. In my field there is this idea of quantum sneaker-net. This is far more useful than my answer and potentially solves a major problem in the field I work in, but is also totally off the wall. The basic idea is that you can make an extremely high speed low latency network for quantum communication by shipping giant refridgerators around the world on ships (using a quantum effect and the existing [non-quantum] internet). The paper is here: https://www.nature.com/articles/srep36163 https://www.nature.com/articles/srep36163 Re 3: Somebody here pointed out pingfs which seems to take the idea to a whole new extreme, but reading the website it seems like it was already being worked on in 2011. I doubt anyone implemented my answer in any way. It was somewhat intentionally impractical.

gumby 7y ago

This solution is how RAM was implemented on some early computers, with acoustical memory in mercury delay lines. Crazy! I saw one at the computer history museum and realized that it weighed tons!