Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I would like to submit a portion of my code for Code Review, and I have done my best to comment the code (and include essential parts that may aid understanding of the program) for your convenience! Any optimisation that would increase the speed of the running of the program would be appreciated!

The program is designed to check through Civilization 5 mods to ensure that they have not make mistakes and finds mistakes that users would have to load the mod (which takes a long time compared with the amount of bugs that can be present) to discover. My program performs this task much faster than the conventional method and so will be useful for modders like myself to quickly check their mods.

First a little housekeeping:

private static Vector<RequiresWhere> statements = new Vector<RequiresWhere> (); //all the requires-where added by the program or the user live here
private static Vector<String> baseGameStatements = new Vector<String> (); //when the base game files are run through this system, any errors are put here, and ignored later on

/*
 * This is the sort of format for the requires-where statement
 * taking the first requires as an example:
 * the program requires that in the "register" there is at least two Tags with identifiers that match ANY CIVILIZATION.*
 * (This is important, CIVILIZATION_ENGLAND and CIVILIZATION_FRANCE must both be present twice in the following tables)
 * in the Tables with an identifier of:
 *     Civilization_UnitClassOverrides
 *     Civilization_BuildingClassOverrides
 *     Improvements
 * the required tag can be present in any of those tables,
 * so one CIVILIZATION in Improvements and another in Civilization_UnitClassOverrides would qualify the two required
 */
public static void reset()
{
    addRequires(2, "(Civilization.*ClassOverrides)|Improvements", "CIVILIZATION.*", false);
    addRequires(10, "Civilization_SpyNames", "CIVILIZATION.*", false);
    addRequires(1, "Civilization_CityNames", "CIVILIZATION.*", false);
    addRequires(1, "Civilization_Leaders", "CIVILIZATION.*", true);
    addRequires(1, "Leader_Traits", "LEADER.*", true);
}

private RequiresWhere(int numMatches, String location, String tag, boolean exact)
{
    this.numMatches = numMatches; //number of matches we want (if exact, well... x == numMatches, if not then could be x >= numMatches)
    this.tag = tag; //the regex for the tag name we want (every different tag must have the requiredMatches, if tagA has 1 match and tagB has numMatches - 1 matches they don't add up!
    this.location = location; //and the tables it belongs in
    this.exact = exact; //do we require exactly numMatches or >= numMatches?
}

and then on to the part of the code that needs to be optimised:

/*
 * This method is called from the maincode routine, if store is true, the results are added to the baseGameRequires
 * otherwise they are printed out to syso
 */
public static void executeRequires(boolean store)
{
    for (RequiresWhere requires : statements) //for every requires-where statement
    {
        for (Table table : Table.getRegister().values()) // for every table in the register
        {
            if (table.isPrimary()) // make sure it is primary
            {
                for (String identifier : table.getRows().keySet()) //for every primary tag in this table
                {
                    if (identifier.matches(requires.tag)) //if this tag matches our regex
                    {
                        int x = 0; //we have 0 matches
                        String tableNames = ""; //present in "" tables

                        for (String name : Table.getRegister().keySet()) //for every table name in the register
                        {
                            if (name.matches(requires.location)) //if this table matches our location regex
                            {
                                tableNames += tableNames.isEmpty() ? String.format("%s", name) : String.format(" or %s", name); // add this table to our names just in case there is not enough matches
                                for (Vector<Row> rows : Table.getTable(name).getRows().values()) // for every group of same name rows in this table
                                {
                                    for (Row row : rows) // for every row in this group
                                    {
                                        for (Tag<?> tag : row.getTags()) //for every tag in this row
                                        {
                                            if (tag.get() instanceof String) //if the data in the tag is a string
                                            {
                                                if (((String) tag.get()).equals(identifier)) // does this match our primary tag that matches the tag regex?
                                                {
                                                    x++; //register a match
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }

                        if ((x != requires.numMatches && requires.exact) || (x < requires.numMatches && !requires.exact)) //if we don't have enough matches
                        {
                            String error = String.format("MISSING REQUIREMENT: The tag %s is required to have %s %s entr%s in table %s, it currently has %s", identifier, requires.exact ? "exactly" : "at least", requires.numMatches, requires.numMatches == 1 ? "y" : "ies",  tableNames, x);
                            if (!baseGameStatements.contains(error) && !store) //if this error wasn't present in the baseGame (our users don't need to care about this)
                            {
                                System.out.println(error); //then print to syso
                            }
                            else if (store) // if this IS the baseGame
                            {
                                baseGameStatements.add(error); //store for later!
                            }
                        }
                    }
                }
            }
        }
    }
}

If anybody has questions about the purpose or specifics of the code, please ask!

Just in case anybody needs to know, this is the layout of the table register:

Table class contains a HashMap of Table instances paired with their name, which are accessed by getTable(String name) or getTables() for everything

A Table contains an HashMap <String, Vector<Row>> which stores Rows, grouped by their primary tag's name

a Row contains an LinkedHashMap of Tag <?>s which can be varying types such as int or String mapped to their name.

The Tag has a name and a ? data field.

When the program first loads it checks the base game XML files and loads all the data into the register. It performs a few checks (which are not important here) then we get to our code above. After running all the base game data through the system it performs the same checks and parsing for a chosen mod (which is combined with the base game data), it therefore goes back through the code above, and makes sure that the mod contains tags in places where the game's Lua code demands they are (a big cause of error for modders is not knowing about the undocumented requirements and having the game complain because of it)

EDIT: I have applied a lot of the below suggestion and also precompiled the regex for location and tag. This has taken the total runtime of the function down from ~15% to 2.8%! Any other suggestions would be appreciated!!! Especially with the algorithm itself!

share|improve this question

1 Answer 1

up vote 7 down vote accepted

First, some basics:

  • Vector is a class that is deprecated.... actually, not deprecated, but discouraged....

    As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

    and, if you need synchronization, which you do not, then you should be looking at java.util.concurrent.* classes anyway.

  • Code Style: Java Code Style recommends putting the opening brace { on the same line as the condition/statement for if/for/while structures....

  • If you are using String.format(...) anyway... you may as well replace:

     tableNames += tableNames.isEmpty() ? String.format("%s", name) : String.format(" or %s", name);
    

    with:

     tableNames = String.format("%s%s%s", tableNames, tableNames.isEmpty() ? "" : " or ", name);
    

    but using a StringBuilder will be a good option too.

With those small things out of the way .... and, by the way, the change from Vector is not really 'small', it has a big performance impact.... then you can look at the bigger items.

  • Function extraction - break out your inner loops in to discrete functions. This has a number of performance benefits too, primarily related to how the Java code is compiled when it is used often.

  • Use for (Map.Entry<K,V> ... : map.entrySet()) {...} loops, instead of map.values() and map.keySet()

In all, I would also wonder whether it is an option to keep things at the XML level, and use something like Saxon, or JDOM (which I maintain) as a mechanism for running XPath expressions on. Saxon has the ability to index the documents, and XPath expressions end up being very efficient if the document is big, and static... which this may be. The Saxon index will be more efficient than what you have (or it should be).

share|improve this answer
    
Yeah, I was sure I stopped using Vector a long time ago, but I guess in my conversion process I forgot to change them to ArrayList (or I might have been experimenting with some multithreading and didn't put them back). As for the braces, I find it difficult to read code which has the brace on the opening line of a statement, but I do acknowledge that it is the norm! As for the Map.Entry, what benefits does it have over my current method, or is it just convention, because I don't see how it would produce more efficiency, by just looking at it and I am curious to know why :) –  J_mie6 Apr 21 at 16:34
    
Furthermore, with Function extraction, how much do you think it would improve operation? And if I used this system, would the use of aggregate functions also help when using this system? As for the Saxon or JDOM, the program is designed so that after the first run of the program all of the base game data is serialized to bypass several checks and the parsing the next time the program is loaded. This leaves the mod files, which tend to be quite small to be processed during standard runtime, would you still say that JDOM would be a good idea? –  J_mie6 Apr 21 at 16:49
    
Two different things: Java tends to compile code at the method level when Jit happens. You only call your method once, it will never be compiled. If you factor out the inner functions to be separate, then they will get compiled after a number of invocations (depends on JVM), and will be faster. –  rolfl Apr 21 at 16:52
    
JDOM/Saxon would require significant rewrite, for marginal potential gains.... Each of them will deal with a single document at a time... I understand your code aggregates the documents in to one place. I am uncertain whether you will see any benefits. –  rolfl Apr 21 at 16:54
2  
Well, as above, your suggestions (and precompiling the regex statements) have effectively cut the run-time down by 81%! so a great improvement. This leaves another check consuming 85% of runtime so I will post that one too in a separate thread –  J_mie6 Apr 21 at 19:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.