Performance of Software

I was reading a little about scala these days and think that it's a cool language that would probably make my life a lot easier. For example, the CardCompiler is hard to use; you have to go through a few hoops to implement new effect parsers. I think that I am on the right way, but there is much room for improvement in terms of usability.

But today I don't want to talk about Scala, but software performance. One point with Scala is that it largely uses immutable objects, putting copying over mutating existing objects. The first thought when you hear this is probably how much memory this would waste and that it will also need more processing power all the data has to be copied.

However, performance doesn't mean to use as little resources as possible. It means to use the resources you have the best possible. And nowadays, the resource we have but use the least are multiple processors.

Modern processors work on the edge of physical possibilities. Circuits are not thicker than a few atoms, and currencies are so small that you can almost measure the number of electrons flowing. At this scale, quantum effects matter, and this means randomness. That's about the reason why (semiconductor) processors don't get faster any more and increasing speed does only occur by parralelism.

Writing software that works parallel, however, is hard, because multiple threads can access the same resource at the same time and thus wreak havoc. Which leads back to immutable objects: Data corruption can only occur when writing. when every access is read-only or creates a copy, nothing bad can happen.

This leaves one question: How bad is copying really? Well, every copy you don't need any more can be garbage collected, so memory should not really be a concern. Memory size is also not as restricted as processor speed, so there should be enough potential to support memory-heavy rather than processor-heavy software.
Garbage collection itself, however, uses the processor. It finds objects that are no longer accessed by any thread; that means that it is not constrained to work in the program's normal flow and can work in its own thread. As the garbage collector is not really interested in the objects, it can even be spread to multiple threads if necessary.

Copying itself uses processing power, and can take some time for large objects. Usually, the only type of large objects are arrays. There are really not many possibilities: boolean, byte, short, char, int, float, long, double, Object. All these take up to 8 bytes to store. All that stays are the indexes of arrays, which can go into several millions. If we stay with immutable objects, this is really the only bottleneck we have to deal with, because you don't need to copy the array's content objects, as they can't change.

I guess this wasn't all that interesting to read, but I really wanted to speak this out: parallelism is the future of software, parallelism is hard, so any attempt to make it easier, for example by using immutable objects, is a step into the right direction

To URI or not to URI

I'm not an English native speaker, so don't blame me if this Shakespeare reference is not recognizable. Maybe "URI or not URI" would fit better for pronunciation...

Anyway, I'll brighten up the situation for anyone who doesn't know URIs: "URI" stands for Uniform Resource Identifier, and the "not to URI" part of the title refers to "URL", Uniform Resource Locator. Seriously, I don't know what the difference between them is supposed to be, just that they behave pretty differently in Java.
(And for anyone who thinks, "Well, so you do know the difference?" No, the Java classes are an implementation of a specification that I don't understand, and not even really know. I know, however, how the implementation behaves. If this behavior follows the original specification, which was not made for the Java language but presumably for the internet, I don't know.)

So, from my point of view, both URIs and URLs are meant to identify some sort of resource, like a network drive of some web site.

• In Java, you can directly connect to a URL and read from and write to it. You can't do that for a URI, but you can convert between both forms (if the resource is legal in both representations).
• The equals() and hashCode() methods of URL perform a name space lookup, making them very slow. URLs are therefore poor choices for map keys, for example for caching downloaded files.

So, it seems like a tied match. The first one is "obvious", you can see it in the API that URI can't directly open connections. equals() and hashCode() being slow is so subtle that there is an entry in FindBugs, an Eclipse plugin that helps to find common programming mistakes, which is how I learned about it.

The third difference I've experienced so far is very subtle and unexpected, and it is the real reason for this post. wow, about time to get to the point...

You can represent a file inside a Jar (or Zip) archive using a URL or URI; both work. You can also "resolve" a relative URL/URI against another one to get an absolute one. But the combination of both only works with URL!

jar:file:/path/to/archive.jar!/path/inside/archive/

jar:file:/path/to/archive.jar!/path/inside/archive.txt

are both legitimate URIs/URLs. Say, you want to resolve "hello.txt" against these, you expect:

jar:file:/path/to/archive.jar!/path/inside/archive/hello.txt

jar:file:/path/to/archive.jar!/path/inside/hello.txt

however, this works only with URLs. A URI won't be able to resolve and will just return "hello.txt"

I said that I recently reimplemented TreeProperties, and I did it based on URIs. As you might guess, resolving paths relative to some context is pretty important for a tree structure. Finding the bug was very annoying, because reading from a Jar file, or even multiple Jar files, is not something I have years of experience with. Fixing the bug was way easier once I sorted out its origin.

I'd like to end this post with another Shakespeare quote:

"But none come to mind. I hope I have at least fooled you with the quotation marks. Just be aware or the differences between Uniform Resource Locators and Identifiers"

Migrating to Maven

This week, I've finally done what I wanted to do for a very long time: I migrated my project to Maven. Warning: Non-programmers will probably be hopelessly bored.

Maven is a build system with many capabilities that are probably beyond my current recognition. For me, it means essentially these things:

• Managing dependencies to external libraries, such as Dom4J, an XML API, and also to the different projects that belong to LaternaMagica, like TreeProperties.
• For an Open Source project, this also means that I don't have to care that others have all the required libraries, because they can find and download them on-demand. Having the right configurations in the development environment is not that important this way. As a downside, it makes Maven pretty much a requirement for working with my code, but that's just like English is required to read my blog: it's good to know English, no matter what.
• Automatic testing and generation of source, binary and documentation archives, or "snapshots"

I said I wanted to do this for a long time. If you're asking why I haven't done it earlier... well, I was dumb. I couldn't get my Eclipse installation working with the Maven plugin. The problem was... that my eclipse installation was owned by root (the administrator, for all the poor Windows users out there^^) and installing the plugin simply didn't do anything as I didn't have the rights.

So finally, everything is alright. I have totally rewritten TreeProperties and Utils, and also greatly reworked LaternaDoc, which finally does what it should. More on those another time ;)

Last Known Information with Undo

Last Known Information is one of the hardest parts of the Magic rules to implement. It is important when handling effects that use a card that changed zones, for example Persist ("When this permanent is put into a graveyard from the battlefield, if it had no -1/-1 counters on it, return it to the battlefield under its owner's control with a -1/-1 counter on it.") or Swords to Plowshares ("Exile target creature. Its controller gains life equal to its power."). These effects happen when the card is already in the graveyard/exile, but need information of the card when it was on the battlefield. For us, this seems very natural, but from a programming point of view, we have to save the relevant values long enough so that interested effects can look it up.
The two main questions of this concept are already in the previous sentence:

• What values are "relevant"?
• What is "long enough"?

An this is where Undo steps in! Why store the values separately when we can travel back in time and look at the original ones? with that approach, there is no chance that we need a value that was not saved - because we look at the original.
Well, when we talk about time travel, of course there are problems: We have to get back to the future after looking up the needed information, but this is only possible if we didn't change history: The game will discard any actions that lie in the future if we change the past. Unfortunately, even simply looking up the power of a creature will change the past, because it results in evaluating continuous effects etc.
Well, I have another science fiction reference up my sleeve to save the day: If we must not change history, "simply" do it in a parallel universe: Create an exact copy of the game up to the point in the past we need to look up the information, then use it in our regular space-time continuum.

So much for the theory of time travel and parallel universes, the reality is a bit more complex, though. I think I can eventually work it out so that this is possible. This is also the way I expect a potential AI to work: Try out multiple variants in a parallel universe and do the best in the real universe.
But right now, only regular time travel is possible, with the limits set by changing history. The problem is that I can't transfer actions between games yet: If you tap a creature, I can't copy that action and execute it in another game, because the action stores the permanent that was tapped, which is exclusively associated with that game. The solution probably needs hashing or another type of identifier associated with each part of the game.

I hope you enjoyed the short Science-Fiction sequence. I definitely did, and I would never have guessed to talk about Time Travel and Alternate Universes as a serious metaphor for a programming problem.

Simultaneity: Warp World

The first time I mentioned simultaneity is with combat. It was just a coincidence that this was the first time, but it is very reasonable, because simultaneity happens very often during combat: Technically, creatures become attacking creatures simultaneously, then the same happens with blockers, damage etc.

Simultaneity means multiple things, and I'm not sure if I have a full understanding of these. I'll take the example of Warp World, which is a classic example for discussing timing:

Each player shuffles all permanents he or she owns into his or her library, then reveals that many cards from the top of his or her library. Each player puts all artifact, creature, and land cards revealed this way onto the battlefield, then does the same for enchantment cards, then puts all cards revealed this way that weren't put onto the battlefield on the bottom of his or her library.

First, all permanents are shuffled into their respective owner's library, triggering from leaving play. All these abilities see all the cards leaving play, meaning that an ability like "leaves the battlefield" sees all the permanents. There is no variant where that ability leaves early and isn't active when the permanents leave play.

The "then"s in the card's text neatly separate the parts that happen simultaneously. All "enters the battlefield" abilities of cards trigger for cards that enter the battlefield at the same time as them; it seems like the abilities are active just a little earlier than they are in play... it's a little awkward in my opinion.

now hold on - Auras with "Enchant Enchantment" won't make it on the battlefield, because Enchant is not a triggered ability. The Comprehensive rules don't specify a wording for Enchant but rather give it extra rules. It feels, however, like a replacement effect, just like "As ... enters the battlefield" (which don't use the stack at all - they are effects generated by static abilities).

Lands with additional costs, like the painlands, are worded like this, because if it was a triggered ability, you could play the mana ability in response to the cost. So, just like "Enchant Enchantment" enchantments (^^) don't make it, lands like "As ... comes into play, return a land you control to your hand. If you don't, put ... into your graveyard instead." won't, too. Champion, however, is a triggered ability, so your champions can survive. you can even enchant the creatures you wish to exile, because the triggered abilities won't resolve or even be put onto the stack until Warp World finished resolving.


One last thing: after resolving the spells, all the abilities are put onto the stack, in an order depending on player seating and player choice. you can put abilities from entering the battlefield on the stack earlier that those from leaving the battlefield, even though these happened in another sequence...

Damage

I just re-read my post about destruction and realised I should show what it took me to implement damage. This might not be my most interesting post, as it is just code, but maybe some of you are interested. Get ready... there are about 200 lines of code coming for you!


public abstract class DamageEvent extends ReplaceableEvent {
    private MagicObject source;
    private int         ammount;
    private boolean     combat, preventable;
    
    public DamageEvent(MagicObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        this(you(ofInstance(affected)), source, ammount, combat, preventable);
    }
    
    public DamageEvent(Player affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        this(ofInstance(affected), source, ammount, combat, preventable);
    }
    
    public DamageEvent(Supplier affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(affected);
        this.source = source;
        this.ammount = ammount;
        this.combat = combat;
        this.preventable = preventable;
    }
    
    public MagicObject getSource() {
        return source;
    }
    
    /**
     * This method can be used by replacement effects that prevent or increase damage.
     */
    public void setAmmount(int ammount) {
        this.ammount = ammount;
    }
    
    public int getAmmount() {
        return ammount;
    }
    
    public boolean isCombatDamage() {
        return combat;
    }
    
    public boolean isPreventable() {
        return preventable;
    }
}



public class DamagePlayerEvent extends DamageEvent {
    private Player p;
    
    public DamagePlayerEvent(Player p, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(p, source, ammount, combat, preventable);
        this.p = p;
    }
    
    public Player getPlayer() {
        return p;
    }
    
    @Override
    protected boolean execute0() {
        CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");
        
        //118.3a. Damage dealt to a player causes that player to lose that much life.
        getPlayer().getLifeTotal().loseLife(getAmmount());
        
        ed.end();
        
        return true;
    }
}



public class DamagePermanentEvent extends DamageEvent {
    private static final Predicate legalAffected  = and(isIn(ofInstance(BATTLEFIELD)),
                                                                       card(or(CREATURE, PLANESWALKER)));
    
    private static final Predicate isPlaneswalker = card(has(PLANESWALKER));
    //TODO implement wither and lifelink
    private static final Predicate hasWither      = alwaysFalse();
    private static final Predicate hasLifelink    = alwaysFalse();
    
    private CardObject                          permanent;
    
    public DamagePermanentEvent(CardObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(affected, source, ammount, combat, preventable);
        if(!legalAffected.apply(affected)) throw new IllegalArgumentException(
                "affected must be a creature or planeswalker permanent: " + affected);
        permanent = affected;
    }
    
    public CardObject getPermanent() {
        return permanent;
    }
    
    @Override
    protected boolean execute0() {
        CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");
        
        //118.3b. Damage dealt to a planeswalker causes that many loyalty counters to be removed from that
        // planeswalker.
        if(isPlaneswalker.apply(getPermanent())) {
            //TODO remove counters
        }
        //118.3c. Damage dealt to a creature by a source with wither causes that many -1/-1 counters to be put on
        // that creature.
        else if(hasWither.apply(getSource())) {
            //TODO add counters
        }
        //118.3d. Damage dealt to a creature by a source without wither causes that much damage to be marked on
        // that creature.
        else {
            getPermanent().setMarkedDamage(getPermanent().getMarkedDamage() + getAmmount());
        }
        //118.3e. Damage dealt to an object or player by a source with lifelink causes that source's controller to
        // gain that much life, in addition to the damage's other results.
        if(hasLifelink.apply(getSource())) {
            getSource().getController().getLifeTotal().gainLife(getAmmount());
        }
        
        ed.end();
        
        return true;
    }
}


I don't really like this code, because it has the effects of damage hard coded, but I think it's fine for now. extracting these effects later if it's necessary shouldn't be too hard, as the different effects of damage will only be mentioned here, so I can safely delay this task.

Trying out the card editor

I just tried out my card editor to download "a few" cards; all the vanilla creatures and old (non-pain) dual lands. If I haven't done anything wrong in my gatherer search, there are 177 vanilla creatures. it's in fact not so easy to search for textless cards; I had to use the regular expressing "m/^$/" ("m/.../" is the gatherer identifier for regexes, "^$" essentially means "the beginning of the text immediately followed by the end")

by the way, I haven't done a full fledged form for gatherer searches; I did the search on the web site and pasted the search URL into my program. takes me much less time^^

there were two problems: first, my download just discontinued after 89 cards. Looking at what card that was, it was Little Girl from Unhinged with a half mana symbol. Second, even after refining my search to exclude Un-cards, my program only wound up downloading 100 cards. my workaround for that problem was simply to download the other cards by reverting the sort order^^



so, putting things short, I now have over 200 cards implemented, including 177 vanilla creatures, 10 classic dual lands, 10 SHM/EVE dual lands, 5 basic lands, Wrath of God, Damnation and Llanowar Elves. It's really time for combat^^