HN Explorer

Ask HN: I have to analyze 100M lines of Java – where do I start?

87 points by user1241320 ↗ HN
As part of a huge "let's see what's going on here and re-build this from scratch" they dumped the whole code repository on me and my team.

We've started parsing it and tried to work on extracting abstract syntax trees and all that.

Any idea would help us a great deal.

Thanks.

125 comments

[ 3.2 ms ] story [ 101 ms ] thread
bilalhusain
Please elaborate. Why is there need for extracting ASTs? Is it a single 100M line of Java source file? AFAIK Java has limitations on method size. If code is already organized into file and methods try to come up with some sort of UML representation. (I am assuming you are trying to understand the code base, not profiling or doing code analysis.)
MaxBarraclough
Seconded.

> I have to analyse [...]

> We've started parsing it and tried to work on extracting abstract syntax trees and all that.

Why? How will this help? What are you really after?

user1241320
Not a single line. The whole Java codebase.
MaxBarraclough
That doesn't answer my question.

How does parsing ASTs help accomplish the goal? What is the actual goal here? What is meant by 'analyse'?

stuaxo
Start with a static analysis tool - it will find lots of small possible bugs, by fixing them you will get good coverage of the code and insight into the structure + it will be better at the end.
jacquesm
Callgraph. Then document the larger chunks, working your way down.

It's like having a map versus having no map at all.

And 100M lines? Are you sure there is no code generator at work here?

user1241320
It's code that's been developed and it's been running for decades, I'm afraid.
jacquesm
How does that stop you from making a callgraph?

(On the off chance that you don't know what that is: http://en.wikipedia.org/wiki/Call_graph)

user1241320
It doesn't. I was just answering about the code generator thing you mentioned.
jacquesm
100M lines of java code developed 'line-by-line' would make it one of the largest software projects that I've ever heard about.

Without telling you directly that you should disqualify yourself (after all I don't know you), if you don't have the knowledge about the tools employed to deal with medium sized projects (say up to 1M lines) how on earth will you deal with 100 times as much?

klibertp
> 100M lines of java code developed 'line-by-line'

If it's not generated, then it may be "versioned" that way. I saw projects where the entire codebase was copied over to new directories tens of times, and no previous "version" was ever deleted.

But, after giving it some thought, 100 mloc is really MUCH, like in 50x more than anything I directly worked with. It does sound kind of improbable, but hey, it could happen :)

leoc
So ... is (some of) this 100M lines the output of a code generator which has since itself been lost? If so, then it seems like a good idea to take a good hard second look for it: scour every nook and cranny for source code, object code, documentation or any surviving evidence (old developer emails?) of how it worked.
venkyk
developed in java and running for decades? how long has the language been around?
jacquesm
19 years. But sun was pushing it quite aggressively at enterprises so it is not rare to see big java installations that are now 15+ years old.

And those are not the most fun to work on.

arethuza
I started using Java in early '95 (having begged a copy from someone at Sun) and I seemed to be one of the first people writing stuff outside of Sun.
jebblue
I started in August 1995 when I first heard about it, which I thought was when they released it but it may have had a variety of trickle releases.
arethuza
I was working on something slightly similar (embedding a VM into a browser) during '94/'95 and was a bit miffed when I first heard of Java....

However, I did think Java was rather good and when I co-founded a start-up in mid '95 we positioned ourselves as a "Java company" - which was no bad thing in the long term as we were in a reasonable position when Netscape, Novell and IBM later decided they wanted to support it. Indeed our 2 round of VC investment was led by Novell - quite unusual for a UK company at the time...

sgt101
I was doing Java in a very mainstream UK company in 1998; but we were leading edge and it became "standard" in 2000ish. By 2003 there were 100's of developers using it where I worked.
Satoshietal
Java was apparently introduced in 1995, and thus has not quite been around for "decades". Close, but 19 years is not quite "decades". LOL

Presumably somebody didn't write 100M lines of code on Day 1.

bjackman
You haven't really described your goals: What do you want to extract from your analysis? Metrics to tell you what's "wrong" with the existing code base? Some sort of model of the system's semantics?
jacquesm
At a guess, understanding and ability to fix/change, that's the usual with projects like these, bringing the code back into a state of maintenance which could be described as 'under control'.
user1241320
We'd love to know what these lines do. For example what part of this codebase deals with the DB and what part does not. And then go deeper.

The final goal is to re-do what these lines do :(

jacquesm
> The final goal is to re-do what these lines do

That is quite possibly a huge mistake. (And a very costly one too!)

[deleted]
(comment deleted)
grey-area
100, 000, 000 lines of code is a huge amount and would take you over 1000 days just to read at 1 line per second, and 1000 man-years to fully understand. If your final goal is to rewrite all of it you are probably doomed to fail. You should first ask yourself (and your clients) some simple questions about why this insane project has been dumped on you and what the goal is:

What is the order of priority of services - which services/apps are critical, and which are not very important?

Which services actually need to be rewritten and which are working just fine?

Which services have a clearly defined interface and can be rewritten?

Which tests are in place to test the existing services, and which will you have to write?

I wouldn't touch the code till you have answered those questions, and once you have those answers, having some sort of overview of code coverage etc is going to seem less important, because it will become obvious which bits need to be touched first (the ones that are both mission critical and broken), and which bits you can easily isolate.

You will find it very very hard to show concrete progress if you try to change all of this code at once, in a global way (for example by tidying up every single reference to a db to use a new db interface, or things like that). If you do, you'll never reach your final goal, and end up spending months tidying up without actually delivering value to the business.

johan_larson
Yes, a "rewrite" is the wrong way to think about this project. A typical programmer might be able to produce 10K lines of production code in a year, which means it would take 10,000 engineer-years to rewrite it all.

The OP needs to think in terms of stewardship, not complete reconstruction, and make improvements by small steps as a gradual process.

I talked about a similar problem here: http://short-sharp.blogspot.ca/2012/08/fixing-broken-codebas...

[deleted]
(comment deleted)
darrelld
Start at the main function. See how things get setup and walk through the code from there. Keep notes on the structure and flow of things (if any). There isn't really an easy way to do this unless it had been documented properly before.

AstroGrep is a good Windows based tool that allows you to search within file so you could use it to find which files spit out a particular output to screen.

Not sure what you mean by using ASTs though.

jacquesm
AST = abstract syntax tree.

With 100M lines your process will take many years.

eklavya
Am I missing something or are you saying that making an AST like a compiler will help you understand a huge codebase better and faster?
jacquesm
No, an AST will not help but a call graph certainly would (it shows you how the various routines are organized in graph form, who calls who).

An AST for 100M lines would be absolute madness, a call graph just might work and I'm somewhat hoping that it turns out to be either a ton of generated or duplicated code.

I also wonder if the OP isn't out of his depth based on the question(s) asked.

klibertp
"making an AST like a compiler" will give you a semantic - as contrasted with textual - understanding of the code. Especially with how much data Java encodes in its source, this makes it a very good base for running automated analysis and visualisation tools, perhaps written by yourself.

In general having AST is always better than having a plain text file, unless you want to read it. But then you can easily dump AST back to text whenever you want.

Yeah, making AST will help you analyse your codebase programmatically which in turn will let you understand the codebase better and faster. This is some very basic programming knowledge, I think. Or is it not? Some comments here don't know what AST even is - is this the state of PL knowledge in the mainstream? Lisp and Smalltalk people would be very, very sad if it was so.

jacquesm
I disagree an AST would help with a project this size, it's just unmanageable.

You'd be better off to start with just the build scripts and build tools.

ASTs are great for increasing understanding of much smaller projects but for something this size you'd likely end up with very little to show for your effort except the crashlogs of your tools.

You need to go 'coarse' before you can go 'fine' on something this magnitude.

This is not a 3 week project, just mapping the thing properly will take (man)years.

eklavya
Yeah I only came to know about AST around a year back. I guess I am not just that competent but I can not imagine someone trying to make sense of a codebase using ASTs. Mostly it's read the code/modify the code/debug the code for me.

I have written some Scheme and I still can't say I need to screw around with ASTs. May be I will be enlightened some day?

A UML diagram for this level of hugeness would be a really useful thing according to me, much much better than an AST.

klibertp
I probably overreacted, sorry for this - working on programming languages and programming tools is not what most of programmers do (obviously) and that's the only domain where you need to know about what you can use AST for.

As for this:

> A UML diagram for this level of hugeness would be a really useful thing

we actually agree 100% here. What I mean is that having AST is meaningless by itself, but you need AST if you want to generate UML diagram from the code. Or generate a callgraph. Or find similarities or duplication in the code. Or indeed perform any kind of automatic code transformation.

So extracting AST is a first step to developing your own tools for working with a codebase. And with a codebase of this size you just have to write your own tools, adapted to the nature of this particular codebase. So while "trying to make sense using ASTs" really is a bit hard to imagine, trying to make sense of a codebase using all the tools AST enables you to write is what I had in mind.

dmead
why would you need the ast?

if given a large chunk of code to maintain i'll usually run doyxgen on it to generate the xmlish kind of chart that it makes. at least it gives me a roadmap to start, but it's not super great.

jebblue
I used this on some projects, works well. Building with the Dot diagrams is a good visualization, in the final HTML documents choosing Classes | Class Hierarchy shows them.
mattgibson
Just curious: what application needs 100M lines of anything?
user1241320
It's not just one application. It's many of them.
kubiiii
Why not (sounds easy eh?) go one application at a time? Are there interactions between apps? Maybe you can start with documenting all the interaction (~ api). Then you'd go deeper in each app.
eCa
I agree with kubiiii.

Since a rewrite is in the card (hopefully) there is something wrong with the entire system.

* Identify where the applications interact with each other.

* Identify the most problematic applications.

* Rewrite those (starting with the smallest) while trying to keep the interfaces between applications constant.

And involve end users as much as possible.

ufmace
A few ideas that have worked for me in the past:

Map the control flow. This code/app/whatever is doing something in production right now. What tells it to start? How does the control flow from the start point to the stuff that takes in data to the stuff that writes the output or does whatever this app does? Whatever the options for how it works are, where are they set, how do they make it into the core of the application to affect whatever it does?

Map the data flow. Input must be coming into this thing somewhere. Find where it reads it in, where it writes it out, and how it gets from one to the other, what data structures and methods it passes through on the way.

sp332
As a first pass, try deleting as much code as possible :) If there are files or whole projects that aren't needed anymore, they're just slowing down your analysis. Also some dead-code analysis could be helpful, at least in broad strokes. You could instrument the code with a test coverage tool, then run the code instead of the tests to see what code gets reached.

Edit: You could also look for duplicated code, and quickly refactor that to just be in one place.

sergiosgc
For rewrite from scratch projects, I always start by identifying the use cases covered by the application. You don't need the code for that. Just run the application and identify what it is that it does. Then, work backwards. For each use case, use the existing code as specification of the use case behavior.

At 100 million lines, I'd suspect this is either an extremely large project, where a rewrite from scratch is inadvisable, or that there is a code generator at work. If it is the latter, you want to analyze the code generating source, not the end result.

Anyhow, generically, for a first contact with a new code base, code coverage tools are a good start, as is a call graph debug run of the project. It'll let you spot dead code as well as hot code (code being called at every run of the application). It'll highlight the important and non-important code parts, allowing you to read less code and get a grasp on the architecture.

rkalla
This, 100x this.

You and your team don't just have to build an understanding of the code (e.g. frameworks, patterns, DB's, etc.) but the app itself so you can truly understand it's purpose.

Your rewrite won't (hopefully?) also be 100mm lines so being able to understand the high level purpose of the app completely and then diving deep from there, you may (hopefully) find many places where the system can be simplified.

Are you really not exaggerating? 100mm lines of source? Yiiiikes...

fleitz
Yup, start the profiler up, use the application, check the call graph.

At 100 MLOC the code base is probably a complete mess.

Also, simian is probably your friend as it will identify large chunks of duplicate code.

As well source control can be your friend, the older the source is the more likely it is to contain useful code. The files with the most changes will usually be where the bugs are.

jacquesm
Why did this get downvoted? It's actionable and on topic.
stronglikedan
I could be wrong, but I think the "M" means thousands in this case. I know it means thousands when dealing with inventory UOMs. 100 million lines just seems like a lot, even for a code generator, and not something that would be turned over to a single team.
crpatino
I don't think there are that many companies with ~10^8 LOC code bases in the world, let alone for a single product[1]:

Facebook(webapp): ~310^7 LOC Linux Kernel: ~210^7 LOC Windows XP: ~5*10^7 LOC My impression is that 10 million LOC codebase is relatively common... but past that the size of the organization (company or volunteers) needed becomes a major sorting criteria.

[1] http://www.wired.com/2013/04/facebook-windows/

atmosx
Yes but these project are no dumped to a team to re-write them all the often, are they?

The way I get this, his team is limited in personnel and resources and kinda overwhelmed by the project. I'm sure Facebook/Linux (OS devs)/Microsoft are not exactly out of developers.

crpatino
All the more reason to sharpen the good old resume... if there was not a typo in the OP numbers, this smells a lot like an intentional career killer.
n1ghtmare_
I realize Facebook is not a trivial software, but seriously - this large? I heard this before and I just don't get it.
crpatino
Errata. Numbers should read as: Facebook(webapp): ~3 * 10^7 LOC. Linux Kernel: ~2 * 10^7 LOC. Windows XP: ~5 * 10^7 LOC.
johan_larson
Identify the users. Figure out who actually does anything with the system. They'll be invaluable as you try to determine what part of the system are active.

Look for a test suite. You'll need one once you start making changes, to keep from breaking anything. If necessary create one based on actual jobs run of the system. You want integration tests, for big parts of the system, rather than unit tests.

Once you have a test suite, start with dead code analysis. Any codebase as big as this one will have a lot of accumulated cruft that is just getting in the way. Delete it.

[deleted]
(comment deleted)
logn
Source to UML: http://www.architexa.com/

Getting call paths: https://github.com/gousiosg/java-callgraph

Line coverage from instrumented jars: http://emma.sourceforge.net/

For this type of request, I'd push back and say, let's identify very small parts of this and begin rewriting those one at a time in an isolated project. Kind of an agile rewrite that will combine the legacy project with the slowly rewritten one. Use the tools to identify parts of the project than can be isolated. Build new interfaces or services to let the old project communicate with the new one. Get a history of the source repository to see where recent edits are and prioritize those to be rewritten first (presuming they want a rewrite to lower maintenance costs).

Igglyboo
What are you actually trying to accomplish? "Analyze" is a broad term.
rashthedude
What type of application has 100 million loc's? Windows 7 has 40 million lines of codes so I'm wondering why type of application/software it is.
gerhardi
I have a quite strong feeling that certain complex automated systems within financial services / insurances domain could reach those LOC levels. Including all the frontend side, internal backend logic, possible web services, internal tools, tests, tens to hundreds of interfaces to different kinds of external services, report generation, libraries, etc.
user1241320
BINGO!
jacquesm
BINGO all you want but if you're at liberty to disclose such things (or to confirm them) you should have included it in your original write up.
thound
Sure, 'cause if he/she had, you would already have found a solution! No need to be rude nor arrogant, even more if pointlessly so.
jacquesm
No, it's just that such information makes a huge difference to those that try to make sense of the question, especially a poorly defined and somewhat confusing question as posed here.
kjs3
How exactly does knowing it's an insurance/finance application magically change the answer to "how to get my head around 100m lines of Java code"? Is there some "financial java code analysis" tool or technique that's so completely distinct from "engineering java code analysis" or "healthcare java code analysis" that it deserves a snotty, condescending retort?
jacquesm
An 'Ask HN' with this level of input is not a guessing game where the people that try to help have to play 'bingo' with the asker for information that may or may not be important for the answer. If there is context available and the asker is free to talk about that context then it should be supplied up-front.

There is nothing snotty or condescending about that, but there is something very weird about this whole thread, I wished I could put my finger on it.

michaelvkpdx
With a codebase like that, it's better to look at it through the users' eyes, rather than trying to reverse engineer the business from the code. Things that look like bugs in the code may actually be features for the users, or may have been absorbed so long ago that they've fundamentally changed the nature of the business.

You don't need to understand the whole codebase. It will take years. Best to focus on what the users need and analyze small chunks. If it's truly 100M lines, there's not going to be any semblance of consistency in the code.

You can also slap New Relic on it and you may be amazed at what you learn, right away.

Don't waste too much time trying to understand all the code. Focus on a couple issues first, make some hypothesis, and then see how well your understanding of the code fits the bigger picture. Refactor and repeat.

user1241320
Any human line-by-line/application-by-application analysis is (for this particular discussion) out of the scope.

The size of the thing and the way we thought we were going to work is quite different.

For instance, suppose we produce AST for all the routines/pieces of logic/you_name_it we wanted to then find similar patterns or clusters that would give us hint to then work on a "pareto-like" way.

As already stated it's not ONE project, it's an old (but still running), poorly-documented codebase produce in decades around this big firm we work for.

jerven
Don't try to figure out how the code does what does yet. Figure out what systems exists inside it:

  1.  What kind of modules?
  2.  Which servers/hardware?
  3.  Which databases/datastores?
  4.  What systems talk to what?
  5.  What test systems exist or existed?
  6.  Which api/frameworks where used?
  7.  Who is currently working on them/maintaining it?
  8.  Is anyone left who used to?
  9.  Why is a rewrite on the table?
  10. Is there any way you can work on smaller pieces at a time?
  11. What are the pain points of the current users (will tell you what area to focus on)?
  12. Can you document what comes in and out?
In my experience with such large code bases, there is never one way to do things. i.e. I once worked on a smaller system with 4 ways to talk to the same database. On one with 100 million lines I would expect even more ways to rome ;)

If you do want to go down the static analysis path, start with existing tools before trying to build your own. If needed get external help for this.

A 100 Million lines of code is not so bizarre. The project I work on is currently about 300,000 lines and a project some 300 times larger is quite imaginable for me.

jacquesm
Code complexity does not increase linearly.

100 M lines is stupendous.

jerven
Not really, my project is 3 FTE for 8 years. Double it to 16 years and then multiple the number of developers by 100.

Consider a large enterprise having 300 developers in multiple teams, I am not at all surprised that they can manage to write 100 million lines or so. Also I think this is really a system of systems, and in my experience probably has large parts developed by the lowest bidding firms. Which when software is developed for 10 years or more means more than one way to do the same thing.

Also having to deal with lots off ancient systems and working around weird bugs probably fixed years ago. You know things like bugs in Java 1.2 on HP-UX and stuff like that, or errors in Oracle 7i etc...

Plus functional duplication because team A did not know subteam C2 build the same thing...

Editing my comment instead of replying to the excellent comment by @jacquesm as hn does not allow me to reply to the reply.

Actually completing the transfer of a codebase like that is unlikely to a new team without much much more of a handover. But some high/middle frustrated with the current system manager asking a team to start rebuilding before it gets shut down a few months/years later is very possible. An other plausible option is a corporate take over... But then I would expect a very experienced team to work on it who do not need to ask HN for this kind of thing.

I personally have been in a situation where code moved between companies and no documentation or old developers where available. Not as large as this only a 1 or 2 million lines of code/xml. But I am no longer surprised by the stupid acts that large corporations can perform.

And this must be systems not just one. You can't build a single jar file of 50+ millions of lines of code than could have loaded in a JVM around 1.3.1 on even high end hardware for the time.

jacquesm
How realistic does it sound to you that a codebase that size would be transferred to a new team without any of the old team, outside of a hack of a bank or a reversal of some outsourcing decision or something like that?

Typically the value of such a codebase is determined by the quality of the team maintaining it and the degree to which it is documented.

Complexity of software constructs is not linear and enough books have been written about simply multiplying and dividing manyears and lines of code that I don't think we need to hash that out all over again. See 'the mythical man-month' and many similar books and articles.

smm2000
Productivity in LOC/developer/day drops dramatically with increase of the team and code size. Every change requires extensive testing, figuring out interdependency, etc. If codebase is bad, it can take multiple days to make 10 lines change.
radicalbyte
When you go above the 1m-or-so LOC it gets much easier to move to more data-driven designs.

Of course the OP could be including all test cases, data etc in his LOC; in which case you could easily reach the hundred-million LOC mark...

atlantic
1) determine the use cases of the different applications involved (ie, what is each one used for, how does it fit into the company's workflow)

2) treat each app as a black box, understand the major data flows involved (which data sources is it interacting with? is it doing reads or writes? which tables)

3) treat each app as a black box, and try to understand the interactions between each app and any external components (other apps, web services, etc)

4) identify the overall architecture, determine the class hierarchy for each app, identify the major classes and functionality

By this stage you should be ready for a rewrite. At no point do you need to go into the code in any great depth.

radicalbyte
Do you and your team have experience of Java development?

Your question sounds like something that someone with either no real experience and/or no experience of an object-oriented language would ask.

100 million lines is a lot of code. Why do you need to "parse it to extra the AST"? That's crazy.

Do you have the original design documents and architectural documentation? If you do, read it.

klibertp
Downvoted.

Even if the design docs would exist, it would take months to read them, without any guarantee that they correspond to the reality.

Meanwhile, automated analysis of actual code can give you at least high-level overview of the codebase and maybe a hint where to start digging. Getting AST is a first step required for most automated tools to do their work.

EDIT: I acted too rashly and downvoted your post before I realized what are we really talking about. Sorry about this. I still am convinced that automatic, static analysis of the code is the way to go, but you obviously don't deserve a downvote for having different opinion. I'll try to make it up to you by being more careful in the future :)

radicalbyte
Hahaha, no problem.

Static Analysis would be my second step, but first I'd have a look at the architectural documentation. I can't imagine that a project of this size wouldn't at least have a Powerpoint explaining the structure and concepts of the code.

Then it's time to start using tools.

andrewljohnson
The code length has to be overstated, by including libraries, generated files, or data files. Is any real code that long?

I bet the core java code the team actually wrote is 2 orders of magnitude smaller.

jacquesm
And they knew what they were doing.
Satoshietal
99M loc for dealing with timezones. Before it was a library call.
pacofvf
Yeah, the LOCs in one of the biggest banks in the world is close to 10M (including: Trading[eq & ficc] , Credit, Mortgages, Wholesale, Wealth Management, Quant, Risk, and also UIs, tests , reports , recons, interfaces) , I don't think a task like that was given to single person, usually with that base of code a big IT consulting company is hired.