15 October 2014

Network Algorithmics by Varghese

I skimmed Network Algorithmics by George Varghese (2005). This book presents common tricks used at the OS, hardware, and architecture levels to prevent network bottlenecks. Here are 15 principles listed on the first page.

Number Principle Example
1 Avoid obvious waste Zero-copy interfaces
2 Shift computation in time
2a Precompute Application device channels
2b Evaluate lazily Copy-on-write
2c Share expenses, batch Integrated layer processing
3 Relax system requirements
3a Trade certainty for time Stochastic fair queuing
3b Trade accuracy for time Switch load balancing
3c Shift computation in space IPv6 fragmentation
4 Leverage off system components
4a Exploit locality Locality-driven receiver
4b Trade memory for speed Processing, Lulea IP lookups
4c Exploit existing hardware Fast TCP checksum
5 Add hardware
5a Use memory interleaving and pipelining Pipelined IP lookups
5b Use wide word parallelism Shared memory switches
5c Combine DRAM and SRAM effectively Maintaining counters
6 Create efficient specialized routines UDP checksums
7 Avoid unnecessary generality Fbufs
8 Do not be tied to reference implementation Upcalls
9 Pass hints in layer interfaces Packet filters
10 Pass hints in protocol headers Tag switching
11 Optimize the expected case Header prediction
11a Use caches Fbufs
12 Add state for speed Active virtual circuit list
12a Compute incrementally Recomputing CRCs
13 Optimize degrees of freedom IP trie lookups
14 Use bucket sorting, bitmaps Timing wheels
15 Create efficient data structures Level-4 switching

14 October 2014

Diablo 3 - item sets

Modern item games like Diablo 3 (D3) use a mechanic called sets: when used together, certain items unlock particular bonuses. For example in D3, Litany of the Undaunted increases attack speed, The Wailing Host increases crit chance, and used together they give 15% extra gold from monsters. Item sets is an old mechanic - the Diablo 2 expansion already had some in 2001.

Sets in D3 are a great mechanic for at least two reasons. First, sets let developers encourage the use of certain skills. Since the bonuses from set items nearly always provide more damage than regular non-set items, players use them. For example, the Marauder set for Demon Hunters requires the use of sentries, a skill that would not be used otherwise because its AI for picking a target is unpredictable. Second, set items are a great mechanic also because they give players a goal. When I dropped my first set item and saw the set bonuses, I immediately wanted other items in the set.

Sudden increase in power

End-game starts after reaching level 70. Reaching level 70 by yourself takes roughly 15 hours. Difficulty from then on can be measured by the Greater Rift (GR) level your character can reach. Set bonuses are so powerful that they make your character jump multiple GR levels at once. For example, going from 5 set items to 6 can double your character's effective damage or toughness, and make you reach 5 or 6 GR levels higher. This explains why the Ring of Royal Grandeur, which reduces the number of items needed for set bonuses by 1, pretty much a wild-card for all your sets, is such a game-changer. These sudden increases in power sometimes surprise players, but I think each bump makes them suddenly feel very powerful. Interestingly, back in 2013, sets used to be as good as non-set legendary items.

Vague descriptions or hidden mechanics?

The descriptions of D3 set bonuses are often vague, and require the player to check the forums and Youtube videos for details. Here are two examples.

Marauder set

This is a Demon Hunter set. The 2-piece bonus is straightforward: it gives 500 dexterity (on top of the approximately 500 dexterity already contributed by each set piece).

The 4-piece bonus makes the Companion skill call all possible companions (instead of only one). Do passive effects from the Companion skill (e.g. the boar increases life regeneration) apply as well? And do all active effects trigger when I use the skill? The answers are not written in the description, but people figure it out quickly by trying.

The 6-piece bonus reads: Sentries cast your equipped Hatred spenders. After trying it out, I realized that sentries have a different rate of fire for each spender: Cluster Arrow (massive area damage) seems to happen only every 5 shots, whereas Elemental Arrow (small multi-target damage) the rest of the time. Looking at high-level Demon Hunters, most wear Tasker and Theo, which increases the attack speed of your pets by 40-50%. Are sentries pets? (Yes!) And how can I make my sentries use Cluster Arrow more often? (You can't!) Theorycrafters figured it all out by analyzing game frames one by one and sharing their findings. But is the average player supposed to read the forum to improve their character?

Zunimassa set

This is a Witch Doctor set. The 2-piece bonus gives 250 intelligence and grants 30 Mana per Kill. Is it only when my character performs the killing blow on a monster? Does it also work when it's one of my pets? Does it also work when it's another player?

The 4-piece bonus reads: Your Fetish Army (FA) lasts until they die. This is straightforward, and it made me think about the passive skill Fetish Sycophants (FS). FS seems to combo well with FA: When you hit enemies with your spells, you have up to a 10% chance to summon a dagger-wielding Fetish to fight by your side for 60 seconds. There are several problems with this apparent FA-FS synergy.

First, why the up to? What makes the rate be less than 10%? That is where theorycraft comes to the rescue. The community found out that one can have at most 15 active FS at the same time. So the rate of FS trigger is 10% until 15, at which point it becomes 0%. The description of FS should also mention this cap of 15.

A second problem is the easy confusion between the two types of fetishes. 1) Witch Doctors can have many pets: a Gargantuan, zombie dogs, FA fetishes, FS fetishes, and mimics. FA and FS are both fetishes, so intuitively, they must benefit from the same bonuses. 2) Why excluding FS from the 4-piece bonus when the effect from the Carnevil helm applies to both FA and FS? 3) The distinction between FA and FS is not for game balance: in practice, it's very easy to maintain 15 FS active all the time by speeding through monsters.

Why so vague?

I can see several reasons:

  • Practicality: the developers want to be able to modify the bonus (through hotfix or patch) without modifying the description.
  • Brevity: a precise description may require too much space in the item tooltip.
  • Practice: figuring it out by trial is more visceral than by just reading the description.
  • Theorycraft: explaining everything spoils the fun of theorycrafters.

Uselessness, sub-optimality, and combinatorics

Some sets are clearly underpowered compared to others. The Witch Doctor Invoker set and the Demon Hunter Shadow set are only useful when your character gets hit. Sadly, in D3, the best defense is offense: the goal is to kill monsters quickly enough that they don't kill you. Therefore these sets end up never being used (except the 2-piece Shadow set in hardcore mode, maybe?).

The Natalya set is not useless, but rather suboptimal. Both the 2-piece and 3-piece bonuses increase damage slightly and enhance mobility (more discipline means more Vaulting). The 4-piece bonus reduces the cooldown of Rain of Vengeance by 2 seconds for each enemy you kill. RoV has a base cooldown of 30 seconds, and does 1000% area damage for 5 seconds, so the set seems very interesting. In practice however, it is difficult to keep monsters grouped in an area for 5 seconds. So while some players use the 2- and 3-piece bonus, nobody cares about the 4-piece bonus. I wonder if the set would be more used if the cooldown was reduced by 2 seconds for every enemy hit (instead of killed).

ArcheAge boasts 120 classes, but it's only because players can pick 3 skill trees among 10, ie C(10,3) = 120 different combinations of skill trees. I don't think that all combinations are efficient, but ArcheAge achieves such diversity simply by leveraging combinatorics on 10 coherent sets of skills. In D3, a player using a Demon Hunter can pick 6 active skills among 24, so that's a total of C(24,6) = 134k different builds. Add to this that each active skill has 4-5 runes, and that there are also another 4 passive skills (5 if we count the Hellfire Amulet) to pick among 18. That's billions of combinations! Yet the only sustainable Demon Hunter builds actually played are minor variations around the same 6 skills. That is because the Marauder set forces players to pick these skills. Moreover, I really liked combining multiple 3- and 4-piece sets together, but the 6-piece Marauder took all the spots. I wish D3 had 1) more 4-piece sets and fewer 6-piece sets, and 2) combinations between sets, not just between sets and legendary items (e.g. Marauder and Tasker and Theo)