0
\$\begingroup\$

Joining a project with some crazy LINQ sorting statements and after refactoring by the team using a custom comparer we found out that it is so slow for some data that you actually think it is an infinite loop.

How to fix this performance issue but still maintaining the sorting requirements?

private static IEnumerable<PolicyTransactionItem<Subject>> GetSubjectsForChangeTracking(
            List<PolicyTransaction> transactions)
        {
            var ebcidicSortComparer = new EBCDICSortComparer();

            var subjects = (from t in transactions
                            from s in t.PolicySubjects
                            select new PolicyTransactionItem<Subject>()
                            {
                                Item = s,
                                PolicyNumber = t.PolicyNumber,
                                FromDate = t.EffectiveDate,
                                ToDate = t.TermExpirationDate,
                                CoverageKey = t.CoverageKey,
                                AmBestNumber = t.IssuerAmBestCompanyNumber
                            });

            subjects = subjects
                    .OrderBy(t => t.Item.FirstName, ebcidicSortComparer)
                    .ThenBy(t => t.Item.MiddleName)
                    .ThenBy(t => t.Item.LastName, ebcidicSortComparer)
                    .ThenBy(t => t.Item.NameSuffix)
                    .ThenBy(t => t.Item.DOB ?? DateTime.MaxValue)
                    .ThenBy(t => t.Item.SSNFromDb, new EBCDICSortComparer(true))
                    .ThenBy(t => t.Item.GenderCodeFromDb)
                    .ThenBy(t => t.Item.RelationToInsuredCodeFromDb)
                    .ThenBy(t => t.Item.RelationToPolicyHolderCodeFromDb)
                    .ThenBy(t => t.Item.DLNumberFromDb, ebcidicSortComparer)
                    .ThenBy(t => t.Item.DLStateFromDb, new EBCDICSortComparer(false))
                    .ThenByDescending(t => t.FromDate)
                    .ThenByDescending(t => t.ToDate).ToList();

            return subjects;
        }

public class EBCDICSortComparer : IComparer<string>
    {

        public EBCDICSortComparer(bool emptyStringLast)
        {
            _emptyStringLast = emptyStringLast;
        }

        public EBCDICSortComparer()
        {
            _emptyStringLast = false;
        }

        private readonly bool _emptyStringLast;

        static readonly int[] AsciiToEBCDICArray = new int[256]{
                        0, 1, 2, 3, 55, 45, 46, 47, 22, 5, 37, 11, 12, 13, 14, 15,
                        16, 17, 18, 19, 60, 61, 50, 38, 24, 25, 63, 39, 28, 29, 30, 31,
                        64, 79,127,123, 91,108, 80,125, 77, 93, 92, 78,107, 96, 75, 97,
                        240,241,242,243,244,245,246,247,248,249,122, 94, 76,126,110,111,
                        124,193,194,195,196,197,198,199,200,201,209,210,211,212,213,214,
                        215,216,217,226,227,228,229,230,231,232,233, 74,224, 90, 95,109,
                        121,129,130,131,132,133,134,135,136,137,145,146,147,148,149,150,
                        151,152,153,162,163,164,165,166,167,168,169,192,106,208,161, 7,
                        32, 33, 34, 35, 36, 21, 6, 23, 40, 41, 42, 43, 44, 9, 10, 27,
                        48, 49, 26, 51, 52, 53, 54, 8, 56, 57, 58, 59, 4, 20, 62,225,
                        65, 66, 67, 68, 69, 70, 71, 72, 73, 81, 82, 83, 84, 85, 86, 87,
                        88, 89, 98, 99,100,101,102,103,104,105,112,113,114,115,116,117,
                        118,119,120,128,138,139,140,141,142,143,144,154,155,156,157,158,
                        159,160,170,171,172,173,174,175,176,177,178,179,180,181,182,183,
                        184,185,186,187,188,189,190,191,202,203,204,205,206,207,218,219,
                        220,221,222,223,234,235,236,237,238,239,250,251,252,253,254,255
                        };

        public int Compare(string x, string y)
        {
            if (x == null)
                return 1;

            if (y == null)
                return -1;

            if (string.Equals(x, y))
                return 0;

            var xChars = x.ToCharArray();
            var yChars = y.ToCharArray();

            if (xChars.Length == 0)
                return _emptyStringLast ? 1 : -1;

            if (yChars.Length == 0)
                return _emptyStringLast ? -1 : 1;

            for (var i = 0; i < Math.Min(xChars.Length, yChars.Length); i++)
            {
                var charItemX = xChars[i];
                var charItemY = yChars[i];

                var ebcdicItemX = AsciiToEBCDICArray[charItemX];
                var ebcdicItemY = AsciiToEBCDICArray[charItemY];

                if (ebcdicItemX != ebcdicItemY)
                    return ebcdicItemX > ebcdicItemY ? 1 : -1;
            }

            return x.Length.CompareTo(y.Length);
        }
    }

[UPDATE]

Debugging one by one the fields it turns out the problem is in .ThenBy(t => t.Item.SSNFromDb, new EBCDICSortComparer(true)). When I try to debug the comparer it seems that x and y are both null, always, and it turns out like a "forever loop".

Adding this at the top of the Compare method seems to fix the problem.

if (string.IsNullOrWhiteSpace(x) &&
    string.IsNullOrWhiteSpace(y))
       return 0;
\$\endgroup\$
  • \$\begingroup\$ How about converting the first query to an array, before starting to sort it? \$\endgroup\$ – D. Jurcau Sep 8 '16 at 15:41
  • 1
    \$\begingroup\$ With 11 compares, 2 of them in the loop, yeah, it could be slow. You could easily precompute "_emptyStringLast" as the integer 1 or -1 in the constructor(s) rather than holding on to the boolean. That eliminates 2 compares right off the bat. \$\endgroup\$ – Jesse C. Slicer Sep 8 '16 at 16:21
  • 1
    \$\begingroup\$ And while you're at it, compare the lengths of the strings before converting them to character arrays. That way, zero-length strings don't go through the conversion process. \$\endgroup\$ – Jesse C. Slicer Sep 8 '16 at 16:24
  • 1
    \$\begingroup\$ And finally convert the fields to EBCDIC once (on some temporary objects), then compare those; if it's done in a comparator it will be converted over and over again for no good reason. \$\endgroup\$ – ferada Sep 8 '16 at 16:36
  • \$\begingroup\$ How about determining what bit is causing the slowness by commenting stuff out or stubbing it, then focus on why that bit is slow. \$\endgroup\$ – 404 Sep 8 '16 at 16:39
3
\$\begingroup\$

AsciiToEBCDICArray establish one-to-one relation between EBCDIC and ASCII characters, so you do not have to convert to check whether characters are identical. You need to convert only when ASCII characters are different. So, instead of this:

      var charItemX = xChars[i];
      var charItemY = yChars[i];

      var ebcdicItemX = AsciiToEBCDICArray[charItemX];
      var ebcdicItemY = AsciiToEBCDICArray[charItemY];

      if (ebcdicItemX != ebcdicItemY)
          return ebcdicItemX > ebcdicItemY ? 1 : -1;

you can have:

      var charItemX = xChars[i];
      var charItemY = yChars[i];

      if(charItemX != charItemY)
          return AsciiToEBCDICArray[charItemX] > AsciiToEBCDICArray[charItemY] ? 1: -1;

to save quite a few character conversions.

\$\endgroup\$
  • \$\begingroup\$ ... and .ThenBy(t => t.Item.DLStateFromDb, new EBCDICSortComparer(false)) can be .ThenBy(t => t.Item.DLStateFromDb, ebcidicSortComparer) \$\endgroup\$ – Y.B. Sep 8 '16 at 17:06
  • \$\begingroup\$ Made the changes to the code, the problem is when passing true to the comparer. Investigating why the "loop" now. \$\endgroup\$ – George Taskos Sep 8 '16 at 17:36
0
\$\begingroup\$

And finally convert the fields to EBCDIC once (on some temporary objects), then compare those; if it's done in a comparator it will be converted over and over again for no good reason.

What I suggested is to map, sort, unmap, aka Schwartzian transform:

  1. fetch the values without most sorting except the date sorting,
  2. copy objects into some temporary wrapper that still has a reference to the original object
  3. map to EBCDIC in the wrapper
  4. sort (use a stable one so that the sorting by date is preserved)
  5. return a list with the original objects from the now sorted list.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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