4 ms·

Interesting video. The approach in it is also inspired by meet-in-the-middle, but suffers from a significant deficiency: It requires a lot of memory—90 GiB—enou

Interesting video. The approach in it is also inspired by meet-in-the-middle, but suffers from a significant deficiency: It requires a lot of memory—90 GiB—enough that the author had to borrow their university's compute cluster to conduct a solve, even when written and optimized in C++. Likewise, their "triple DES" presentation discussed another way that would require a database that's terabytes in size (specifically, memory that's O(N^0.5)). Nonetheless, I think it's a good exposition of meet-in-the-middle. What's neat about the method in the post is that it requires O(N^0.5) time and O(N^0.25) memory, which allows running it on an entry-level consumer laptop (hours of time and a few GiB of memory) when implemented even in a dynamically typed, garbage-collected language.

bradknowles 3y ago
MacBook Pro laptops can now be had with 96GB of RAM. And terabyte class databases can be extremely fast if running on SSD.
- deleted 3y ago
  [deleted]
- gwern 3y ago
  It's also not hard these days to fire up an instance on AWS or other cloud service which will have up to a few terabytes of RAM. Plus, you can always just bite the bullet and do it all out of swap - might not be as bad as you fear, and often can optimize whatever you're doing to be more online. There are countless tricks left over from the old days for doing out-of-core operations efficiently, whether disk or tape.
  - bradknowles 3y ago
    If you're firing up anything on AWS with that kind of RAM, you want to make sure you understand how much that's going to cost. The per second cost is always going to look really low and you will tend not to worry about it. However, once you do the math, you could find that you're easily and quickly spending more money than it would cost to buy a machine to run locally with that much RAM.
    - gwern 3y ago
      It's been fine when I've used terabyte instances for dynamic programming stuff similar to OP. You are babysitting it and waiting for a specific answer, not running a permanent service which will hemorrhage $$$ when you forget to turn it off. At dollars an hour, hard to forget...
      - bradknowles 3y ago
        So long as you actually play close attention to it, that's not a problem. The issue is that many people fail to pay close attention, and that's where the money can really rack up.
pjc50 3y ago
> It requires a lot of memory—90 GiB—enough that the author had to borrow their university's compute cluster to conduct a solve I remember something like fifteen years ago we needed a 128GB computer to solve IC modelling (timing closure) problems. While this was reasonably available, the only supplier we could find was gaming-oriented, so we had a blinky light tower PC in the corner of the server cupboard. Anyway, never underestimate the power of a single computer, especially with a GPU.

bradknowles 3y ago

MacBook Pro laptops can now be had with 96GB of RAM. And terabyte class databases can be extremely fast if running on SSD.

deleted 3y ago
[deleted]
gwern 3y ago
It's also not hard these days to fire up an instance on AWS or other cloud service which will have up to a few terabytes of RAM. Plus, you can always just bite the bullet and do it all out of swap - might not be as bad as you fear, and often can optimize whatever you're doing to be more online. There are countless tricks left over from the old days for doing out-of-core operations efficiently, whether disk or tape.
- bradknowles 3y ago
  If you're firing up anything on AWS with that kind of RAM, you want to make sure you understand how much that's going to cost. The per second cost is always going to look really low and you will tend not to worry about it. However, once you do the math, you could find that you're easily and quickly spending more money than it would cost to buy a machine to run locally with that much RAM.
  - gwern 3y ago
    It's been fine when I've used terabyte instances for dynamic programming stuff similar to OP. You are babysitting it and waiting for a specific answer, not running a permanent service which will hemorrhage $$$ when you forget to turn it off. At dollars an hour, hard to forget...
    - bradknowles 3y ago
      So long as you actually play close attention to it, that's not a problem. The issue is that many people fail to pay close attention, and that's where the money can really rack up.

pjc50 3y ago

> It requires a lot of memory—90 GiB—enough that the author had to borrow their university's compute cluster to conduct a solve I remember something like fifteen years ago we needed a 128GB computer to solve IC modelling (timing closure) problems. While this was reasonably available, the only supplier we could find was gaming-oriented, so we had a blinky light tower PC in the corner of the server cupboard. Anyway, never underestimate the power of a single computer, especially with a GPU.