5 ms·

Optimizing a breadth-first search

114 points by yoha 8y ago

megaman22 8y ago
> 100GB of memory would be trivial at work, but this was my home machine with 16GB of RAM. And since Chrome needs 12GB of that, my actual memory budget was more like 4GB. Anything in excess of that would have to go to disk (the spinning rust kind). I hope this is a joke, although it's a little scary totalling up how much Chrome is chewing right now, with just one window and seven tabs open...
frankmcsherry 8y ago
https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
- rrobukef 8y ago
  This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
  - jsnell 8y ago
    As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth. Totally happy to believe I'm wrong about that, though :) [0] https://github.com/apocalyptech/snakebirdsolver https://github.com/apocalyptech/snakebirdsolver
    - frankmcsherry 8y ago
      It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth). The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader: > Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.
      - jsnell 8y ago
        Fair enough, and it's easy to test :) I made a non-iterative DFS, but hardcoded the maximum depth to the optimal solution. On a trivial puzzle that should take <1ms, it takes 6 seconds. The BFS visits 303 states, the DFS 9M (but only 237 unique ones). This is with deduping the states on the path. If we allow the same state on the path multiple times, it'd be 12s, 50M visited states, 239 unique states. This is with a random visiting order, it'd be a bit worse with a static visiting order. This is obviously not fully optimized code (whee, std::unordered_set). But fixing that won't help when we're off by 3-4 orders of magnitude. I think the shape of the search graph of this game just isn't well suited to any form of DFS, there are far too many alternate paths to each state.
        rrobukef 8y ago
        Thank you. It's interesting to see the explosion of states. You could add a cache (per search depth) to deduplicate states again. It will reduce small cycles and the used memory is easier to control. Kudos for the encoding. 0.7 bits per state is dense.
    - OskarS 8y ago
      The linked solver doesn't use iterative deepening, and it saves all states that the DFS solver encounters (negating the advantage of using DFS). I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least. EDIT: read your reply to the other user. Fair enough :)
  - hinkley 8y ago
    I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.
    - AstralStorm 8y ago
      The problem seems to have many early branches making deep searches much less useful.
    - ball_of_lint 8y ago
      It would probably end up with similar memory requirements because it has to dedupe. Naively you would need to store all the visited states anyway just like with BFS. You might see some interesting effects using a bloom filter and an IDDFS. It would turn the whole search probabilistic but might be fast enough that you could run it enough times to remove reasonable doubt.
- danmg 8y ago
  The article is about optimizing the saved state information of the search, not about optimizing the search itself.
  - rrobukef 8y ago
    Yet it's also about solving a problem, that goes out of memory. If there is an equal algorithm that doesn't go out of memory isn't this a valid criticism? The author probably spent some time writing the code, modifying and extending the algorithm. He wrote deduplication code, memory mapping etc. Wouldn't it be interesting to know how iterative deepening performs?
    - AstralStorm 8y ago
      Memorization, deduplication and good data structures should help IDDFS and similar algorithms too.
- agumonkey 8y ago
  wow, I've thought about this for so long .. never would have found this wikipedia page on my own.
stcredzero 8y ago
Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms. There are literally problems that were 1) once covered in freshman year, 2) could once be recognized and solved by CS grads in seconds, 3) stump recent CS graduates, 4) prompt HN commenters to say how they could solve it if given a few days, and 5) come up in conversation if you go to meetups and talk to people doing actual work. How does this relate to BFS? It used to be that someone trained as a computer scientist would look at a data structure or a graph and start running some quick gedankenexperiments: What would happen if I tried to find that with DFS? What would happen if I tried to find that with BFS? Those aren't going to be suitable solutions for all problems, but it's a good place to start thinking. There seem to be a large number of recent grads who can't even get that far.
- hashkb 8y ago
  I clicked on this thread to make a sure-to-be-downvoted ironic comment along the lines of "this isn't appropriate content for HN based on community sentiment regarding whiteboard interviews and what kind of work we actually do at our jobs." There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete.
  - duxup 8y ago
    "There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete." Is that really the case, universities are trying to compete with bootcamps? I don't see much in the way of signs of that.
- taeric 8y ago
  I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. However, few could ever do things in seconds. Nor is there really any benefit in being able to solve something in seconds. Interestingly, to me, it seems our industry was dominated by people that got good at gluing things together. To a very large degree. We bemoan this when we talk about how much more responsive machines used to be, but I think there can be very little denying that computers do more. Granted, I suspect I am at best one of the bad graduates you are referencing. :(
deleted 8y ago
[deleted]

114 points by yoha 8y ago

> 100GB of memory would be trivial at work, but this was my home machine with 16GB of RAM. And since Chrome needs 12GB of that, my actual memory budget was more like 4GB. Anything in excess of that would have to go to disk (the spinning rust kind). I hope this is a joke, although it's a little scary totalling up how much Chrome is chewing right now, with just one window and seven tabs open...

frankmcsherry 8y ago

https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".

rrobukef 8y ago
This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
- jsnell 8y ago
  As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth. Totally happy to believe I'm wrong about that, though :) [0] https://github.com/apocalyptech/snakebirdsolver https://github.com/apocalyptech/snakebirdsolver
  - frankmcsherry 8y ago
    It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth). The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader: > Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.
    - jsnell 8y ago
      Fair enough, and it's easy to test :) I made a non-iterative DFS, but hardcoded the maximum depth to the optimal solution. On a trivial puzzle that should take <1ms, it takes 6 seconds. The BFS visits 303 states, the DFS 9M (but only 237 unique ones). This is with deduping the states on the path. If we allow the same state on the path multiple times, it'd be 12s, 50M visited states, 239 unique states. This is with a random visiting order, it'd be a bit worse with a static visiting order. This is obviously not fully optimized code (whee, std::unordered_set). But fixing that won't help when we're off by 3-4 orders of magnitude. I think the shape of the search graph of this game just isn't well suited to any form of DFS, there are far too many alternate paths to each state.
      - rrobukef 8y ago
        Thank you. It's interesting to see the explosion of states. You could add a cache (per search depth) to deduplicate states again. It will reduce small cycles and the used memory is easier to control. Kudos for the encoding. 0.7 bits per state is dense.
  - OskarS 8y ago
    The linked solver doesn't use iterative deepening, and it saves all states that the DFS solver encounters (negating the advantage of using DFS). I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least. EDIT: read your reply to the other user. Fair enough :)
- hinkley 8y ago
  I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.
  - AstralStorm 8y ago
    The problem seems to have many early branches making deep searches much less useful.
  - ball_of_lint 8y ago
    It would probably end up with similar memory requirements because it has to dedupe. Naively you would need to store all the visited states anyway just like with BFS. You might see some interesting effects using a bloom filter and an IDDFS. It would turn the whole search probabilistic but might be fast enough that you could run it enough times to remove reasonable doubt.
danmg 8y ago
The article is about optimizing the saved state information of the search, not about optimizing the search itself.
- rrobukef 8y ago
  Yet it's also about solving a problem, that goes out of memory. If there is an equal algorithm that doesn't go out of memory isn't this a valid criticism? The author probably spent some time writing the code, modifying and extending the algorithm. He wrote deduplication code, memory mapping etc. Wouldn't it be interesting to know how iterative deepening performs?
  - AstralStorm 8y ago
    Memorization, deduplication and good data structures should help IDDFS and similar algorithms too.
agumonkey 8y ago
wow, I've thought about this for so long .. never would have found this wikipedia page on my own.

stcredzero 8y ago

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms. There are literally problems that were 1) once covered in freshman year, 2) could once be recognized and solved by CS grads in seconds, 3) stump recent CS graduates, 4) prompt HN commenters to say how they could solve it if given a few days, and 5) come up in conversation if you go to meetups and talk to people doing actual work. How does this relate to BFS? It used to be that someone trained as a computer scientist would look at a data structure or a graph and start running some quick gedankenexperiments: What would happen if I tried to find that with DFS? What would happen if I tried to find that with BFS? Those aren't going to be suitable solutions for all problems, but it's a good place to start thinking. There seem to be a large number of recent grads who can't even get that far.

hashkb 8y ago
I clicked on this thread to make a sure-to-be-downvoted ironic comment along the lines of "this isn't appropriate content for HN based on community sentiment regarding whiteboard interviews and what kind of work we actually do at our jobs." There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete.
- duxup 8y ago
  "There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete." Is that really the case, universities are trying to compete with bootcamps? I don't see much in the way of signs of that.
taeric 8y ago
I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. However, few could ever do things in seconds. Nor is there really any benefit in being able to solve something in seconds. Interestingly, to me, it seems our industry was dominated by people that got good at gluing things together. To a very large degree. We bemoan this when we talk about how much more responsive machines used to be, but I think there can be very little denying that computers do more. Granted, I suspect I am at best one of the bad graduates you are referencing. :(

deleted 8y ago

[deleted]