←back to thread

-2000 Lines of code

(www.folklore.org)
506 points xeonmc | 3 comments | 25 Jun 25 19:53 UTC | HN request time: 0.965s | source
Show context
bironran ◴[25 Jun 25 22:55 UTC] No.44382555[source]▶
One of my best commits was removing about 60K lines of code, a whole "server" (it was early 2000's) with that had to hold all of its state in memory and replacing them with about 5k of logic that was lightweight enough to piggyback into another service and had no in-memory state at all. That was pure a algorithmic win - figuring out that a specific guided subgraph isomorphism where the target was a tree (directed, non cyclic graph with a single root) was possible by a single walk through the origin (general) directed bi-graph while emitting vertices and edges to the output graph (tree) and maintaining only a small in-process peek-able stack of steps taken from the root that can affect the current generation step (not necessarily just parent path).

I still remember the behemoth of a commit that was "-60,000 (or similar) lines of code". Best commit I ever pushed.

Those were fun times. Hadn't done anything algorithmically impressive since.

replies(13): >>44382607 #>>44383577 #>>44383660 #>>44384143 #>>44384528 #>>44384875 #>>44385261 #>>44385550 #>>44385861 #>>44386549 #>>44386714 #>>44386823 #>>44388515 #
1. chamomeal ◴[26 Jun 25 10:06 UTC] No.44385861[source]▶
I would love a little more context on this, cause it sounds super interesting and I also have zero clue what you’re talking about. But translating a stateful program into a stateless one sounds like absolute magic that I would love to know about
replies(1): >>44386758 #
2. ninetyninenine ◴[26 Jun 25 12:28 UTC] No.44386758[source]▶
He has two graphs. He wants to determine if one graph is a subset of another graph.

The graph that is to be determined as a subset is a tree. From there he says it can be done in an algorithm that only traverses every node at most one time.

I’m assuming he’s also given a starting node in the original graph and the algorithm just traverses both graphs at the same time starting from the given start node in the original graph and the root in the tree to see if they match? Standard DFS or BFS works here.

I may be mistaken. Because I don’t see any other way to do it in one walk through unless you are given a starting node in the original graph but I could be mistaken.

To your other point, The algorithm inherently has to also be statefull. All traversal algorithms for graphs have to have long term state. Simply because if your at a node in a graph and it has like 40 paths to other places you can literally only go down one path at a time and you have to statefully remember that node has another 39 paths that you have to come back to later.

replies(1): >>44390701 #
3. bironran ◴[26 Jun 25 19:57 UTC] No.44390701[source]▶
kindaaaa....

I oversimplified the problem :). Really it was about generating an isomporhic-ish view, based on some user defined rules, of an existing graph, itself generated by a subgraph isomorphism by a query language.

Think a computer network as a graph, with various other configuration items like processes, attached drives, etc (something also known as a CMDB). Query that graph to generate a subgraph out of it. Then use rules to make that subgraph appear as a tree of layers (tree but in each layer you may have additional edges between the vertices) because trees are efficient, non-complex representation on 2d space (i.e. monitors).

However, a child node in that tree isn't necessarily connected directly to the parent node. E.g. one of the rules may be "display the sub network and the attached drives in a single layer", so now the parent node, the gateway, has both network nodes (directly connected to it) and attached drives (indirectly connected to it) as direct descendants.

Extend this to be able to connect through any descendant, direct or indirect (gateway -> network node -> disk -> config file -> config value - but put the config value on the level of the network node and build a link between them to represent the compound relationship).

Walk through the original subgraph while evaluating the rules and build a "trace back" stack to let you understand how to build each layer even in the presence of compound links while performing a single walkthrough instead of nm (original vertices rules for generation).

As I said, that was a lot of fun. I miss those days.