Running with Code Like with scissors, only more dangerous

19Nov/150

Exploring .dbc files with Dynamic Code Generation, part 4: Optimizing string reads

So far, we’ve written a simple parser for the .dbc file format. I’ve outlined that the .db2 file format is the same in principle, primarily different in the header format.

We do know that premature optimization is the root of all evil. However, I’m going to wager that this optimization is not premature. Let’s consider Item-sparse.db2 for a moment; it has 101 columns and a string table that is 2,762,301 bytes long.

Recall that a string-typed column in .dbc is stored as an integer offset into the string block, a region of UTF-8 encoded strings at the end of the table. This is nice for a lot of reasons; the tables can be read very fast because rows are all the same size, strings can be efficiently localized, and the strings don’t need to be decoded until they’re needed. This last optimization is the one we’re going to look at today.

Delay-loading the strings is a nice optimization. UTF-8 strings, when they contain non-US characters, do not have uniform character lengths. Reading them inline while we read the tables is likely to cause many processor cache misses. How can we optimize? By bypassing them altogether, of course. The simplest way would be to create a property such as “TitleStringOffset” instead of “Title” for these properties, call them integers, and expect the user to call DbcTable.GetString. That would be a fine approach, but in my opinion, would leak implementation details to the user.

Instead, let’s wrap that information into an object – call it DbcStringReference – and allow that string to be retrieved later. What would we need in order to retrieve it later? A reference to the DbcTable that produced it, and the integer offset into the string table. Storing the reference to the DbcTable would keep the DbcTable from being garbage-collected as long as I held any of my entities, so we’ll use a WeakReference instead.

public class DbcStringReference
    {
        private WeakReference<DbcTable> _owner;
        private int _pos;
        private Lazy<string> _val;

        internal DbcStringReference(DbcTable owner, int position)
        {
            if (owner == null)
                throw new ArgumentNullException("owner");
            if (position < 0)
                throw new ArgumentException("position");

            _owner = new WeakReference<DbcTable>(owner);
            _pos = position;
            _val = new Lazy<string>(() =>
            {
                DbcTable table;
                if (!_owner.TryGetTarget(out table))
                    throw new ObjectDisposedException("DbcTable");

                return table.GetString(_pos);
            });
        }

        public override string ToString()
        {
            return _val.Value;
        }
    }

There really isn’t anything stellar here. We validate the constructor arguments, take a weak reference to the owner table, and then create a Lazy<string> which tries to resolve the strong reference, throws if that fails, then returns the string. Once the string has actually been retrieved, it is reused in future instances. Because the value of the string is exposed via the ToString override, string formatting methods like Console.WriteLine and string.Format automatically get the correct value (as do concatenation with strings and usage in UIs).

In order to add DbcStringReference to the list of supported types, we’re going to need to make some modifications to our non-compiled and our compiled code sets. Fortunately, the ConvertSlow method itself doesn’t need to change; all we need to change is the TargetInfo.SetValue<TTarget> method. Add this to the switch statement:

                    case TargetType.StringReference:
                        DbcStringReference sref = new DbcStringReference(table, inputVal);
                        SetValue(target, sref);
                        break;

Don’t forget to add a StringReference value to your TargetType enum:

        internal enum TargetType
        {
            String,
            Int32,
            Float32,
            StringReference,
        }

And add in that return value to GetTargetTypeFromType:

        internal static TargetType GetTargetTypeFromType(Type type)
        {
            if (type == typeof(int))
                return TargetType.Int32;
            if (type == typeof(float))
                return TargetType.Float32;
            if (type == typeof(DbcStringReference))
                return TargetType.StringReference;
            if (type == typeof(string))
                return TargetType.String;

            throw new InvalidDataException("Invalid data type.");
        }

Let’s force slow mode on. Here’s a record definition for item-sparse.db2. (Yes, this is code-generated; I found the updated source).

public class Itemsparsedb2
    {

        /// <summary>ID</summary>
        [DbcRecordPositionAttribute(0)]
        public int ID;

        /// <summary>Quality</summary>
        [DbcRecordPositionAttribute(1)]
        public int Quality;

        /// <summary>Flags</summary>
        [DbcRecordPositionAttribute(2)]
        public int Flags;

        /// <summary>Flags2</summary>
        [DbcRecordPositionAttribute(3)]
        public int Flags2;

        /// <summary>Column4</summary>
        [DbcRecordPositionAttribute(4)]
        public int Column4;

        /// <summary>Column5</summary>
        [DbcRecordPositionAttribute(5)]
        public float Column5;

        /// <summary>Column6</summary>
        [DbcRecordPositionAttribute(6)]
        public float Column6;

        /// <summary>Column7</summary>
        [DbcRecordPositionAttribute(7)]
        public int Column7;

        /// <summary>Price</summary>
        [DbcRecordPositionAttribute(8)]
        public int Price;

        /// <summary>SellPrice</summary>
        [DbcRecordPositionAttribute(9)]
        public int SellPrice;

        /// <summary>Column10</summary>
        [DbcRecordPositionAttribute(10)]
        public int Column10;

        /// <summary>Column11</summary>
        [DbcRecordPositionAttribute(11)]
        public int Column11;

        /// <summary>Column12</summary>
        [DbcRecordPositionAttribute(12)]
        public int Column12;

        /// <summary>ItemLevel</summary>
        [DbcRecordPositionAttribute(13)]
        public int ItemLevel;

        /// <summary>Column14</summary>
        [DbcRecordPositionAttribute(14)]
        public int Column14;

        /// <summary>Column15</summary>
        [DbcRecordPositionAttribute(15)]
        public int Column15;

        /// <summary>Column16</summary>
        [DbcRecordPositionAttribute(16)]
        public int Column16;

        /// <summary>Column17</summary>
        [DbcRecordPositionAttribute(17)]
        public int Column17;

        /// <summary>Column18</summary>
        [DbcRecordPositionAttribute(18)]
        public int Column18;

        /// <summary>Column19</summary>
        [DbcRecordPositionAttribute(19)]
        public int Column19;

        /// <summary>Column20</summary>
        [DbcRecordPositionAttribute(20)]
        public int Column20;

        /// <summary>Column21</summary>
        [DbcRecordPositionAttribute(21)]
        public int Column21;

        /// <summary>Column22</summary>
        [DbcRecordPositionAttribute(22)]
        public int Column22;

        /// <summary>Column23</summary>
        [DbcRecordPositionAttribute(23)]
        public int Column23;

        /// <summary>Column24</summary>
        [DbcRecordPositionAttribute(24)]
        public int Column24;

        /// <summary>Column25</summary>
        [DbcRecordPositionAttribute(25)]
        public int Column25;

        /// <summary>Column26</summary>
        [DbcRecordPositionAttribute(26)]
        public int Column26;

        /// <summary>Column27</summary>
        [DbcRecordPositionAttribute(27)]
        public int Column27;

        /// <summary>Column28</summary>
        [DbcRecordPositionAttribute(28)]
        public int Column28;

        /// <summary>Column29</summary>
        [DbcRecordPositionAttribute(29)]
        public int Column29;

        /// <summary>Column30</summary>
        [DbcRecordPositionAttribute(30)]
        public int Column30;

        /// <summary>Column31</summary>
        [DbcRecordPositionAttribute(31)]
        public int Column31;

        /// <summary>Column32</summary>
        [DbcRecordPositionAttribute(32)]
        public int Column32;

        /// <summary>Column33</summary>
        [DbcRecordPositionAttribute(33)]
        public int Column33;

        /// <summary>Column34</summary>
        [DbcRecordPositionAttribute(34)]
        public int Column34;

        /// <summary>Column35</summary>
        [DbcRecordPositionAttribute(35)]
        public int Column35;

        /// <summary>Column36</summary>
        [DbcRecordPositionAttribute(36)]
        public int Column36;

        /// <summary>Column37</summary>
        [DbcRecordPositionAttribute(37)]
        public int Column37;

        /// <summary>Column38</summary>
        [DbcRecordPositionAttribute(38)]
        public int Column38;

        /// <summary>Column39</summary>
        [DbcRecordPositionAttribute(39)]
        public int Column39;

        /// <summary>Column40</summary>
        [DbcRecordPositionAttribute(40)]
        public int Column40;

        /// <summary>Column41</summary>
        [DbcRecordPositionAttribute(41)]
        public int Column41;

        /// <summary>Column42</summary>
        [DbcRecordPositionAttribute(42)]
        public int Column42;

        /// <summary>Column43</summary>
        [DbcRecordPositionAttribute(43)]
        public int Column43;

        /// <summary>Column44</summary>
        [DbcRecordPositionAttribute(44)]
        public int Column44;

        /// <summary>Column45</summary>
        [DbcRecordPositionAttribute(45)]
        public int Column45;

        /// <summary>Column46</summary>
        [DbcRecordPositionAttribute(46)]
        public int Column46;

        /// <summary>Column47</summary>
        [DbcRecordPositionAttribute(47)]
        public int Column47;

        /// <summary>Column48</summary>
        [DbcRecordPositionAttribute(48)]
        public int Column48;

        /// <summary>Column49</summary>
        [DbcRecordPositionAttribute(49)]
        public int Column49;

        /// <summary>Column50</summary>
        [DbcRecordPositionAttribute(50)]
        public int Column50;

        /// <summary>Column51</summary>
        [DbcRecordPositionAttribute(51)]
        public int Column51;

        /// <summary>Column52</summary>
        [DbcRecordPositionAttribute(52)]
        public int Column52;

        /// <summary>Column53</summary>
        [DbcRecordPositionAttribute(53)]
        public int Column53;

        /// <summary>Column54</summary>
        [DbcRecordPositionAttribute(54)]
        public int Column54;

        /// <summary>Column55</summary>
        [DbcRecordPositionAttribute(55)]
        public int Column55;

        /// <summary>Column56</summary>
        [DbcRecordPositionAttribute(56)]
        public int Column56;

        /// <summary>Column57</summary>
        [DbcRecordPositionAttribute(57)]
        public int Column57;

        /// <summary>Column58</summary>
        [DbcRecordPositionAttribute(58)]
        public int Column58;

        /// <summary>Column59</summary>
        [DbcRecordPositionAttribute(59)]
        public int Column59;

        /// <summary>Column60</summary>
        [DbcRecordPositionAttribute(60)]
        public int Column60;

        /// <summary>Column61</summary>
        [DbcRecordPositionAttribute(61)]
        public int Column61;

        /// <summary>Column62</summary>
        [DbcRecordPositionAttribute(62)]
        public int Column62;

        /// <summary>Column63</summary>
        [DbcRecordPositionAttribute(63)]
        public int Column63;

        /// <summary>Column64</summary>
        [DbcRecordPositionAttribute(64)]
        public int Column64;

        /// <summary>Column65</summary>
        [DbcRecordPositionAttribute(65)]
        public int Column65;

        /// <summary>Column66</summary>
        [DbcRecordPositionAttribute(66)]
        public int Column66;

        /// <summary>Column67</summary>
        [DbcRecordPositionAttribute(67)]
        public int Column67;

        /// <summary>Column68</summary>
        [DbcRecordPositionAttribute(68)]
        public int Column68;

        /// <summary>Column69</summary>
        [DbcRecordPositionAttribute(69)]
        public int Column69;

        /// <summary>Name</summary>
        [DbcRecordPositionAttribute(70)]
        public string Name;

        /// <summary>Name2</summary>
        [DbcRecordPositionAttribute(71)]
        public string Name2;

        /// <summary>Name3</summary>
        [DbcRecordPositionAttribute(72)]
        public string Name3;

        /// <summary>Name4</summary>
        [DbcRecordPositionAttribute(73)]
        public string Name4;

        /// <summary>Description</summary>
        [DbcRecordPositionAttribute(74)]
        public string Description;

        /// <summary>Column75</summary>
        [DbcRecordPositionAttribute(75)]
        public int Column75;

        /// <summary>Column76</summary>
        [DbcRecordPositionAttribute(76)]
        public int Column76;

        /// <summary>Column77</summary>
        [DbcRecordPositionAttribute(77)]
        public int Column77;

        /// <summary>Column78</summary>
        [DbcRecordPositionAttribute(78)]
        public int Column78;

        /// <summary>Column79</summary>
        [DbcRecordPositionAttribute(79)]
        public int Column79;

        /// <summary>Column80</summary>
        [DbcRecordPositionAttribute(80)]
        public int Column80;

        /// <summary>Column81</summary>
        [DbcRecordPositionAttribute(81)]
        public int Column81;

        /// <summary>Column82</summary>
        [DbcRecordPositionAttribute(82)]
        public int Column82;

        /// <summary>Column83</summary>
        [DbcRecordPositionAttribute(83)]
        public int Column83;

        /// <summary>Column84</summary>
        [DbcRecordPositionAttribute(84)]
        public int Column84;

        /// <summary>Column85</summary>
        [DbcRecordPositionAttribute(85)]
        public int Column85;

        /// <summary>Column86</summary>
        [DbcRecordPositionAttribute(86)]
        public int Column86;

        /// <summary>Column87</summary>
        [DbcRecordPositionAttribute(87)]
        public int Column87;

        /// <summary>Column88</summary>
        [DbcRecordPositionAttribute(88)]
        public int Column88;

        /// <summary>Column89</summary>
        [DbcRecordPositionAttribute(89)]
        public int Column89;

        /// <summary>Column90</summary>
        [DbcRecordPositionAttribute(90)]
        public int Column90;

        /// <summary>Column91</summary>
        [DbcRecordPositionAttribute(91)]
        public int Column91;

        /// <summary>Column92</summary>
        [DbcRecordPositionAttribute(92)]
        public int Column92;

        /// <summary>Column93</summary>
        [DbcRecordPositionAttribute(93)]
        public int Column93;

        /// <summary>Column94</summary>
        [DbcRecordPositionAttribute(94)]
        public int Column94;

        /// <summary>Column95</summary>
        [DbcRecordPositionAttribute(95)]
        public int Column95;

        /// <summary>Column96</summary>
        [DbcRecordPositionAttribute(96)]
        public int Column96;

        /// <summary>Column97</summary>
        [DbcRecordPositionAttribute(97)]
        public int Column97;

        /// <summary>Column98</summary>
        [DbcRecordPositionAttribute(98)]
        public float Column98;

        /// <summary>Column99</summary>
        [DbcRecordPositionAttribute(99)]
        public int Column99;

        /// <summary>Column100</summary>
        [DbcRecordPositionAttribute(100)]
        public int Column100;

        /// <summary>Column101</summary>
        [DbcRecordPositionAttribute(101)]
        public int Column101;
    }

Running this in our test harness with item-sparse.db2, enumerating all the records 5 times, this takes 173959ms. Replacing the five string properties with DbcStringReference reduces the time to 173150ms. Hardly any improvement! Now, let’s add in dynamic compilation support.

Add this below the MethodInfo declarations in DbcTableCompiler:

private static ConstructorInfo DbcStringReference_ctor = typeof(DbcStringReference).GetConstructor(BindingFlags.NonPublic | BindingFlags.Instance, null, new Type[] { typeof(DbcTable), typeof(int) }, null);

Add this into the EmitTypeData in DbcTableCompiler:

                case TargetType.StringReference:
                    generator.Emit(OpCodes.Ldarg_2);
                    generator.Emit(OpCodes.Ldarg_0);
                    generator.EmitCall(OpCodes.Callvirt, BinaryReader_ReadInt32, null);
                    generator.Emit(OpCodes.Newobj, DbcStringReference_ctor);
                    break;

And that’s it. The test harness running with string properties takes 13715ms. But… the test harness running with DbcStringReference takes only 2896ms!

Why such a substantial difference? I don’t know for sure, but I can make a supposition. The constructor reference for DbcStringReference can be inlined. That allows the processor cache to be highly efficient. Since we’re not digging into the Encoding.GetString method, we’re saving even more time. Of course, we don’t actually have a copy of the string yet, but if I’m looking for an item by its ID, I’m saving quite a bit of time.

So in summary:

  • String fields, no dynamic compilation: 173959ms
  • DbcStringReference fields, no dynamic compilation: 173150ms, 0.5% improvement
  • String fields, no dynamic compilation: 13715ms, 92.1% improvement
  • DbcStringReference fields, dynamic compilation: 2896ms, 98.3% improvement

Next time? Not sure yet. I’ll get back to you.

Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

ERROR: si-captcha.php plugin says GD image support not detected in PHP!

Contact your web host and ask them why GD image support is not enabled for PHP.

ERROR: si-captcha.php plugin says imagepng function not detected in PHP!

Contact your web host and ask them why imagepng function is not enabled for PHP.

No trackbacks yet.