3 ms·

I use Python's multiprocessing to run A* in parallel with queues communicating between workers and the main thread for code generation. https://replit.com/@Chr

I use Python's multiprocessing to run A* in parallel with queues communicating between workers and the main thread for code generation. https://replit.com/@Chronological/SlidingPuzzle3 https://replit.com/@Chronological/SlidingPuzzle3 (the code shows multiprocessing Processes connected by queues, the README.md explains what the program does) Some algorithms aren't easily parallelisable (at least I haven't worked out how to paralellise them!). My original attempts at paralellising A* didn't work because of communication overhead. But I sharded my data that it searches - each thread searches a different subset of neighbours as A* is a graph search. This lets me paralellise, with 8 threads (when I boosted the repl.it from 2 vcpu to 8vcpu) It would run in 20-40 milliseconds as opposed to 100-300 milliseconds. mgaunard [0] recently told me that there is something called an algorithmic skeleton for parelllisation problems. I've not used any though. https://en.wikipedia.org/wiki/Algorithmic_skeleton https://en.wikipedia.org/wiki/Algorithmic_skeleton I have no exposure to high performance computing unfortunately. Just a deep interest in parallelism. [0]: https://news.ycombinator.com/item?id=36792796 https://news.ycombinator.com/item?id=36792796

pvitz 3y ago
Program synthesis through optimal control or directly through algorithms like A* sounds fun and interesting. If I may, I would suggest to either comment your code or add more details to your README.md, because it is currently quite difficult to understand what exactly is being done here and how.
- samsquire 3y ago
  Thanks for your reply and words. It's path finding between output states of a program. I was inspired by path finding in video games. The path is the discovered program. It's like having a game map where each neighbour of a cell is the potential things you can do at that point in time. For this reason it can be used for unit AI. I think of assembly (and regular) programming as a sliding image puzzle game. My design is based on this intuitive idea that most programming is just moving things around - it's logistics. How much time do you spend marshalling data? REST APIs? To get registers to the value for a CALL instruction, the calling convention, is just moving the right data into the right locations. Imagine you have a start state and an end state. It's a turing machine. State is processor register values and memory values in each memory location. There is a series of state transitions between the start state and end state which is created by an instruction, these are intermediary states. Instructions can be MOV instructions or CALL instructions (function calls) I dynamically generate neighbours of starting from the start state which are potential instructions we can run that get us nearer to the end state. The program searches the space of possible instructions. It infers hidden states caused by functions. The distance heuristic is the number of values that in registers and memory that match the end state. My dream: if you knew the type of every API call, you could provide a start state and an end state and the computer would work out the program based on exploring potential instructions that get us to the target state. This is a much simpler form of program synthesis compared to LLMs. I'll update the README and document the code. I also have a dream of a real time strategy game where you program the computer by telling unit what to do. In most RTS games you can only build, attack but we can do more.
vorticalbox 3y ago
When I need to process sometimes millions of documents from a production mongoDB instance I normally push all the objectID into rabbitMQ then spin up N workers that each fetch a single message at a time.
- rdedev 3y ago
  Is there a reason why you use rabbitmq instead of just using the whats available in the language (I understand if those primitives are hard to work with)
  - tempay 3y ago
    I'd guess they're using multiple machines.
  - vorticalbox 3y ago
    As said people using multiple ec2s to process the data but the biggest reason is so I don't have to run it all in one go. Rabbit is used by a few of our services so is always up, means I can run for a few hours then come back to it another day. Also error handling, if one fails I just don't ack the message, after everything is processed I only have failed ones. Can slowly process the messages to see what is wrong
- samsquire 3y ago
  Thanks for sharing, I think this topic is very interesting. I played about with Kafka consumer groups to get the same effect.
- paulddraper 3y ago
  > then spin up N workers And how do you do that? Because...that is also what the multiprocessing module does.

pvitz 3y ago

Program synthesis through optimal control or directly through algorithms like A* sounds fun and interesting. If I may, I would suggest to either comment your code or add more details to your README.md, because it is currently quite difficult to understand what exactly is being done here and how.

samsquire 3y ago
Thanks for your reply and words. It's path finding between output states of a program. I was inspired by path finding in video games. The path is the discovered program. It's like having a game map where each neighbour of a cell is the potential things you can do at that point in time. For this reason it can be used for unit AI. I think of assembly (and regular) programming as a sliding image puzzle game. My design is based on this intuitive idea that most programming is just moving things around - it's logistics. How much time do you spend marshalling data? REST APIs? To get registers to the value for a CALL instruction, the calling convention, is just moving the right data into the right locations. Imagine you have a start state and an end state. It's a turing machine. State is processor register values and memory values in each memory location. There is a series of state transitions between the start state and end state which is created by an instruction, these are intermediary states. Instructions can be MOV instructions or CALL instructions (function calls) I dynamically generate neighbours of starting from the start state which are potential instructions we can run that get us nearer to the end state. The program searches the space of possible instructions. It infers hidden states caused by functions. The distance heuristic is the number of values that in registers and memory that match the end state. My dream: if you knew the type of every API call, you could provide a start state and an end state and the computer would work out the program based on exploring potential instructions that get us to the target state. This is a much simpler form of program synthesis compared to LLMs. I'll update the README and document the code. I also have a dream of a real time strategy game where you program the computer by telling unit what to do. In most RTS games you can only build, attack but we can do more.

vorticalbox 3y ago

When I need to process sometimes millions of documents from a production mongoDB instance I normally push all the objectID into rabbitMQ then spin up N workers that each fetch a single message at a time.

rdedev 3y ago
Is there a reason why you use rabbitmq instead of just using the whats available in the language (I understand if those primitives are hard to work with)
- tempay 3y ago
  I'd guess they're using multiple machines.
- vorticalbox 3y ago
  As said people using multiple ec2s to process the data but the biggest reason is so I don't have to run it all in one go. Rabbit is used by a few of our services so is always up, means I can run for a few hours then come back to it another day. Also error handling, if one fails I just don't ack the message, after everything is processed I only have failed ones. Can slowly process the messages to see what is wrong
samsquire 3y ago
Thanks for sharing, I think this topic is very interesting. I played about with Kafka consumer groups to get the same effect.
paulddraper 3y ago
> then spin up N workers And how do you do that? Because...that is also what the multiprocessing module does.