1
\$\begingroup\$

A while ago I made a post about optimising the multiplication of every number in an array by 2. With everyone's help I was able to go from 1,500 ns (LINQ) to 30 ns.

So I thought I'd try something harder. The conversion of an int to a Roman Numeral. I have already tried several algorithms one that tested if a numeral is in prefix form like (IV or XC) before adding to the numeral and one that once 4 numerals of the same type were added it backtracked. The following is the best I've come up with where I split the number into units and map each unit to a Numeral. x in the Numeral Map is the power of 10 and y is the amount of that unit.

Any kind of performance optimisation is welcome and don't worry about readability this is just for fun.

The code:


public static Numeral ToNumeral(this int x)
    {
        if (x == 0) return Zero;

        int remaining = x;
        int index = 3;

        int divisor = 1000;


        StringBuilder numeralBuilder = new();

        do
        {
            int digit = remaining / divisor;

            remaining -= digit * divisor;

            divisor /= 10;

            numeralBuilder.Append(NumeralMap.Value[index--, digit]);

        } while (index >= 0);


        return new(x, numeralBuilder.ToString());
    }


    private static readonly Lazy<string[,]> NumeralMap = new(new string[4, 10]
    {
        {"","I", "II", "III", "IV","V", "VI", "VII", "VIII", "IX" },
        {"","X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
        {"","C", "CC", "CCC", "CD","D" ,"DC", "DCC", "DCCC", "CM" },
        {"","M", "MM", "MMM",  "", "",  "",   "",      "",     "" }
    });

Benchmark:

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ Any particular reason why you made the NumeralMap lazy? Ran a crude benchmark and doing it not lazy saves 1-2%, not massive but still \$\endgroup\$
    – ChrisWue
    Dec 6, 2023 at 22:33
  • \$\begingroup\$ Also it would be nice if you could include the Numeral type and the benchmark code you used. This would make it easier to replicate your findings and compare alternate approaches \$\endgroup\$
    – ChrisWue
    Dec 6, 2023 at 22:34

3 Answers 3

1
\$\begingroup\$

memoize

You're unlikely to see more than a few thousand distinct input values.

So allocate a hash or an array, then accept conversion requests. Compute the corresponding result as slowly as you like -- it won't matter. Memoize the result and return it.

Now if you're ever asked for that same conversion again, it costs a hash probe or an array de-reference, and you're off to the races!


Use an LRU technique if you're concerned about aging out ancient unpopular requests.

\$\endgroup\$
4
  • \$\begingroup\$ Memoization is a really good suggestion. However this optimisation works best when we have specific details about the application it will be running in. As you say If I made a million calls to this method and there are only about 3000 possible numerals then caching those numerals is a no brainer. But what If all I want to do with it is to iterate all Numerals from 1 to 1000 and never touch it again? Then we'd probably be hurting the performance. :) \$\endgroup\$ Dec 4, 2023 at 20:19
  • \$\begingroup\$ Yeah, an LRU can limit our memory consumption if we see an access pattern (like counting to 1000) which differs from what we thought at design time the "typical" pattern would be. Monitoring cache hit counters is another way to mitigate such lossage -- if in the last hundred calls we got zero cache hits, then maybe set a disabled = 50 counter, and don't bother memoizing any results until we have decremented that counter down to zero. \$\endgroup\$
    – J_H
    Dec 4, 2023 at 20:24
  • \$\begingroup\$ Still +1 though, this is definitely worth mentioning. \$\endgroup\$ Dec 4, 2023 at 20:25
  • \$\begingroup\$ Very good point but there many not be any discernible pattern at all and the cache may have 0 hits. In this case decrementing a counter and performing the last 100 calls check will hurt performance. I understand these are fringe cases and in practice caching would be beneficial, however I am more looking for optimisations in the code itself. \$\endgroup\$ Dec 4, 2023 at 20:37
1
\$\begingroup\$

Ok been a while but managed to make further optimisations to the method. Splitting the Conversion map into 4 sub-maps made it possible to only perform one bounds check at the start of the method then use unsafe code to quickly access the other maps after. Managed to remove the StringBuilder and replace it with spans to avoid the alocation.

 public override string? ToString()
        {
            if (Value == 0) return "Nulla";

            if (Value > 3999) return null;


            int remaining = Value;


            int digit = remaining / 1000;

            remaining -= digit * 1000;

            ref var thousandsArrayPtr = ref MemoryMarshal.GetArrayDataReference(ThousandsMap.Value);

            ref var thousandsPtr = ref Unsafe.Add(ref thousandsArrayPtr, digit);

            var thousandsSpan = thousandsPtr.AsSpan();


            digit = remaining / 100;

            remaining -= digit * 100;

            ref var hundredsArrayPtr = ref MemoryMarshal.GetArrayDataReference(HundredsMap.Value);

            ref var hundredsPtr = ref Unsafe.Add(ref hundredsArrayPtr, digit);

            var hundredsSpan = hundredsPtr.AsSpan();



            digit = remaining / 10;

            remaining -= digit * 10;

            ref var tensArrayPtr = ref MemoryMarshal.GetArrayDataReference(TensMap.Value);

            ref var tensPtr = ref Unsafe.Add(ref tensArrayPtr, digit);

            var tensSpan = tensPtr.AsSpan();


            ref var unitArrayPtr = ref MemoryMarshal.GetArrayDataReference(UnitMap.Value);

            ref var unitPtr = ref Unsafe.Add(ref unitArrayPtr, remaining);

            var unitSpan = unitPtr.AsSpan();


            return string.Concat(thousandsSpan, hundredsSpan, tensSpan, unitSpan);
        }

enter image description here

\$\endgroup\$
0
\$\begingroup\$

If we completely unroll the loop we can avoid doing bounds checks and some unnecessary assignments and operations.


 if (x == 0) return Zero;

        int remaining = x;

        StringBuilder numeralBuilder = new();


        int digit = remaining / 1000;

        remaining -= digit * 1000;

        numeralBuilder.Append(NumeralMap.Value[3, digit]);


        digit = remaining / 100;

        remaining -= digit * 100;

        numeralBuilder.Append(NumeralMap.Value[2, digit]);



        digit = remaining / 10;

        remaining -= digit * 10;

        numeralBuilder.Append(NumeralMap.Value[1, digit]);



        numeralBuilder.Append(NumeralMap.Value[0, remaining]);


        return new(x, numeralBuilder.ToString());
    }


    private static readonly Lazy<string[,]> NumeralMap = new(new string[4, 10]
    {
        {"","I", "II", "III", "IV","V", "VI", "VII", "VIII", "IX" },
        {"","X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
        {"","C", "CC", "CCC", "CD","D" ,"DC", "DCC", "DCCC", "CM" },
        {"","M", "MM", "MMM",  "", "",  "",   "",      "",     "" }
    });

Benchmark:

enter image description here

If we could somehow run the algorithm without heap allocations that would be fantastic.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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