Search Unity

In Unity 5.0, we shipped the scene and prefab merge tool, and It’s been positively received by the Unity Community. However, we’ve since realized that it doesn’t handle large scenes optimally, especially with respect to memory usage and the time taken to execute processes.

We’ve now worked on a number of changes to improve this, and they will go into future Unity release. As a result, the system is both more memory efficient and faster than other popular merge tools. Here’s a look at what we did.

How it works 10 mile overview

This is roughly how the tool worked to begin with: Three files are read from disk (e.g. mine, incoming and base scene/prefab files) into an in-memory yaml structure exactly like the one we have inside Unity itself.

Now a diff is made between mine and base, and that results in a form of diff-tree describing which operation to perform on the base version yaml to get to the mine version yaml (mine/base diff). The same diff-tree is created for incoming and base (incoming/base diff).

image03

The two diff-trees are now merged into one unified diff-tree (merged diff). This is the first point where conflicts can happen and the conflicts can be resolved by the user. Since the merged diff consists mostly of content from the two source diffs it simply references data inside the source diffs and we make sure their lifetimes exceed that of the merged diff-tree. After this merge is done the source diffs are considered invalid because they may have been rearranged during the merge.

Having the merged diff we can apply that to the base yaml in order to get the end result. This is done by traversing the diff tree and perform its operations on the base yaml. Operations that add new content simply adds a reference to content in the diff and we make sure the diff lifetime exceeds that of the end result. This final step can also result in conflicts because we are doing an additional semantic pass at this point fixing things like circular references created etc.

image02

At this point we can output the result if there are no conflicts. In case there actually are conflicts we need to do some extra work. Since we have no specialized GUI to present the conflicts we prepare three files (mine’, incoming’ and base’) that can be fed into a fallback merge tool e.g. araxis merge. The purpose of these files is to nurse the fallback tool so that it presents as few conflicts as possible. The base’ is simply the result we just created but using values from base where there are conflicts. The mine’ and incoming’ are constructed by doing exactly the same as for getting base’ ie. reading three files, diffing, merging and applying. But instead of using base values we use mine or incoming values respectfully.

Let’s optimize!

To get things going a reasonably large scene (~3 MB) with conflicts was selected. Three other popular merge tools were picked for comparison of speed and memory usage: Diffmerge, k3diff and p4merge. These merge tools can’t do any semantic merging but were, nonetheless, suitable for our purposes (measurements were performed on a debug build of our merge tool).

From the chart below, we can see that worst tool with regard to memory is diffmerge which uses just as much memory as our baseline (the merge tool) with the best tool using 1/8th of the baseline. With regard to time spent, all the other tools perform way better than the baseline with the fastest being diffmerge which uses only 3% of the time of the baseline. The optimization target was to use same amount of time as the fastest tool (diffmerge) and same memory as the tool that used the least memory (k3diff). Ready.. set.. go!

image01

The first glaring issue is that three merges are being done from scratch in the situation where a conflict is present. Much of the setup done by the first can be reused by the next two: Reading and parsing the files, creating mine/base and incoming/base diff. Merging cannot be shared since that is where the outcome differs for the three.

Immutable diffs

Unfortunately, as stated above, the source diffs are rendered invalid when doing a merge and, as such, cannot be reused. This was fixed by making the diff structure immutable. Since c++ doesn’t have built in support for immutability (like e.g. dlang) only logical immutability is used and this works just fine. With immutability comes the issue of having to copy content from source diffs when creating the merged diff instead of simply referencing. However, the fact that the source diffs could now be reused for the two other merges more than doubled the speed of the process, and generated a slight decrease in memory usage.

Float/int removal

Now that merge time had been improved, we moved our attention to memory consumption. The YAML structure replicated the one used inside Unity itself, and it contains a distinction between int,float and string values for leaf nodes in the yaml tree. The is not stored as a union but a int,float and string field. Since the smart merge works on strings most of the time, it makes no sense to keep the former two around. Removing float and int from the leaf struct cut memory usage by 40%.

image00

Threading diffs

Back to improving merge time again. When you have immutability present you have to consider threading since they are a perfect match. By making sure that source structures are also immutable when creating the source diffs it is possible to reuse the source structure for the base and put the creation of the mine/base and incoming/base diffs in two threads.

Threading reads

An extra threading improvement step was to first read and parse the base file and then at that point make a thread for each of the two diffs. Those threads could then share the base file structure but read the mine and incoming file in separate threads.

YAMLScalar* table

Noticing the impact on memory that removing int and float fields had, it seemed to make sense to look in that direction for more memory savings. At that time, realizing that many of the leaf node strings and keys strings in the scene/prefab files are actually the same gave us an idea. It looked very much like a trick that compiler makers have been using forever would fit here: string tables. The idea is to simply keep an array of all strings that are present and have each usage point to that string, thereby removing duplicates. If there are a number of duplicates this can save a lot of space. In our case it wasn’t really a string table but a YAMLScalar table, however the idea is the same.

Pooling

The next idea was to pool yaml nodes instead of simply using new/delete all the time. It speeded up the process, but unfortunately also consumed a bit more memory.

Cloning base

When applying the merged diff on the base yaml the base is modified as the end result. Since we needed to do three merges, that meant reading the base file three times so that each could be modified. Instead of re-reading the base file support for cloning the base in-memory structure was implemented. This speeded up the process significantly.

Subtree hashing

Usually most of the objects in a prefab/scene are unaltered. In order to leverage this subtree, hashing was implemented. During parsing of the yaml files a hash of each subtree is calculated, and that can be used to quickly check if a common subtree has changed when comparing yaml documents.

Map -> vector map

Again, in the name of making the yaml structure a bit more lightweight all std::maps in a yaml node (i.e. maps from yaml node keys to it values) were replaced with std::vectors. This makes perfect sense in that there are usually few fields in a GameObject, or any other class represented in the yaml files, which render the std::map too heavy to use. This also cut down on the time, but, to my surprise, it had an even more positive effect on memory usage.
Thanks to these changes, the merge tool delivered comparable performance to the three tools we tested against. Indeed, once we’d made a release build it outperformed them on both memory and time. Note that the merge tool is performing 3x merges where the other tools are doing 1. It would be very nice to make an in editor GUI for this so that we would only have to do a single merge. Furthermore, a GUI would make it possible to show conflicts that the fallback merge tools cannot such as circular references etc.

Next steps

There is still room for further optimizations, but at this point it is probably not worth working on. Please hit us with any feedback about unhandled conflict cases to the “smart” of the tool. We will then integrate that feedback into the tool as a longer running maintenance task.

As mentioned above, it would really make sense to put a GUI on top of the tool.

Doing all this optimization and refactoring would not have been possible, or would at least have been very troublesome, without an existing test suite to ensure that no regressions were happening after each optimization step.
Thanks for reading!

10 Comments

Subscribe to comments

Comments are closed.

  1. Using git for source control and haven’t been able to get SmartMerge to work. I think I’ve set up the command correctly according to the doc: ‘/Applications/Unity/Unity.app/Contents/Tools/UnityYAMLMerge’ merge -p “$BASE” “$REMOTE” “$LOCAL” “$MERGED”

    Unfortunately, I’m getting the result: Segmentation fault: 11.

    10 GB of free memory, OS X 10.9.5.

    Feel free to email me and let me know what I can provide you in order to help. I’ll fall back to using my normal merge tool, but figured you’d like to know!

    1. I’m having the same problem on OS X 10.10.3 Unity 5.1.1f1

      Normal merge conflict for 'Assets/Puptown.unity':
      {local}: modified file
      {remote}: modified file
      /opt/local/libexec/git-core/git-mergetool--lib: line 130: 26552 Segmentation fault: 11 '/Applications/Unity/Unity.app/Contents/Tools/UnityYAMLMerge' merge -p $BASE $REMOTE $LOCAL $MERGED

  2. Such a lazy ass. Somebody, erase my previous comment.

  3. Where I can find the tool? And maybe some reference on how to use it?

  4. Charlie Helman

    June 3, 2015 at 10:52 pm

    We’ve had some good success with both the Scene merging and Prefab merging on our small team. We also had one colossal failure, where the confusing UI flow caused me to accidentally wipe my scene completely clean (fortunately I had my changes backed up).

    As said in other comments, part of the problem with this feature, which by the way is called Smart Merge, is that there’s little information out there about it. Here’s the official documentation: http://docs.unity3d.com/Manual/SmartMerge.html

    That only covers initial set up. But how do you actually do the merge? Well, through Unity’s Version Control Window! (Window > Version Control)

    I use Perforce, so for me files that need to be merged need to be “resolved” and show up in the Version Control window with a ? icon in the changelist I have them checked out in.

    I right click on that icon, then select Resolve Conflicts. This spawns a window.

    The file in question shows up in this window, and you have three options: “take theirs”, “use mine”, or “merge” (or something like those).

    These are pretty standard source control concepts, but to recap:
    Take theirs: Discard your work and replace it with the latest version of the file.
    Use Mine: Keep your work. Stomp/overwrite the latest version of the file (undoing your colleague’s work).
    Merging: Try combining the files. This is where Smart Merge lives.

    Click Merging.

    From here I’m a little fuzzy, sorry, so please forgive any inaccuracies…

    This spawns another dialog window with some more choices. I don’t remember them exactly, but the one you want is “use semantic merge” or something like that (they should really make it say “Try Smart Merging”).

    This tries to do a Smart Merge. If it works, the window closes, and the file in the version control window will look normal again (I remember wishing there was a confirmation or something).

    If it doesn’t work, there are conflicts, which you can try resolving with the “manual merge” button. I had the impression that the manual merge didn’t utilize the smart merge logic, but maybe I’m wrong.

    If you need to manual merge, *and* you have everything set up correctly, you can compare each conflict in a diff tool like Beyond Compare. In my experience so far, this has actually been pretty manageable.

    Anyway… if there’s enough demand I can write up an actual blog post/tutorial about using Smart Merge. Would anyone find that useful?

    1. Jonas Drewsen

      June 4, 2015 at 3:26 pm

      Remember that this is the way it works if you are using the integrated version control in unity e.g. Perforce. If you are using external version control you need to tell it about the merge tool as shown in the paged you linked. Also, when using the integrated version control and you selected smart merge to resolve a conflict then in case the tool cannot handle all conflicts it will handle as much as possible and then fallback to the merge tool you have set in unity preferences for the remaining conflicts. Those conflicts should be easier to resolve at that point because the tool prepared the files for easier merging using a standard merge tool.

  5. This tool is actually very helpful and will hopefully cut down on the number of duplicate scenes we make in order for us to work in parallel. I’ve never heard of anyone using it though, so I think it would be good if this tool had better visibility. Maybe a video tutorial on it would be good? I’ve only heard of it today myself, so I’ll be spreading the news around.

    While I’ll miss out on the editor integration since I don’t have Unity Pro, it’s great that a CLI tool still exists!

  6. I really think this tool is one of Unity 5’s “best kept secrets”. I have not met or heard too many people who claimed to use it, which is a shame.

    You should probably make some more noise promoting it…

    On anther note – it could be nice to have a UI + some visualization support for this tool (e.g: being able to visualize the impact an incoming changeset or merge is going to have on a scene/prefab).

    Last point – open source it of course !

  7. According to the graph Threading diffs and Threading reads did not change processing time nor memory usage :)

    1. Jonas Drewsen

      June 3, 2015 at 10:39 am

      There is a slight improvement in processing time actually which is hard to spot because the total range of the y-axis is so large. The actual improvement is about 2 seconds.