reduce amount allocation for single number decode #65

jetersen · 2022-04-03T18:18:36Z

Reason for change:
Almost 5x saving for single decode
After further changes by adding a optimized splitter using Span<char> it is only a 2x saving.
By adding a specific GetNumberFrom that handles a single number we avoid creating unnecessary array for long[] and can simply pass back long

I think it would greatly benefit to also actually have a GenerateHashFrom that takes single int/long that would mean single encode decode could be 100% allocation free.

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19044.1620 (21H2)
AMD Ryzen 9 3950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=6.0.103
  Job-RCMHEX : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT

|               Method |        Job |            Runtime |       Mean |     Error |    StdDev | Code Size |  Gen 0 | Allocated |
|--------------------- |----------- |------------------- |-----------:|----------:|----------:|----------:|-------:|----------:|
|        DecodeNumbers | Job-RCMHEX |           .NET 6.0 |   864.4 ns |   3.99 ns |   3.74 ns |   1,359 B | 0.0181 |     152 B |
|   DecodeSingleNumber | Job-RCMHEX |           .NET 6.0 |   799.2 ns |   5.65 ns |   5.28 ns |     190 B | 0.0038 |      32 B |

jetersen · 2022-04-03T18:34:40Z

I may have missed the purpose of the _guards split in the GetNumbersFrom and whether it applies to single.

KeterSCP · 2022-04-04T05:17:28Z

The following code throws NoResultException in your PR if no _guards were used:

var hashids = new HashidsNet.Hashids("salt", minHashLength: 4);

var hash = hashids.Encode(123);
Console.WriteLine(hash);

var decoded = hashids.DecodeSingle(hash); // <-- Exception here
Console.WriteLine(decoded);

jetersen · 2022-04-04T05:26:09Z

Thanks I'll take a look.

jetersen · 2022-04-04T07:37:23Z

I think I managed to find a way to actually improve Decode for multiple numbers without allocating string arrays for guards 😄

jetersen · 2022-04-04T07:39:13Z

@KeterSCP bc5f785 could also apply to multiple decoding.

KeterSCP · 2022-04-04T07:46:05Z

The following code throws NoResultException in your PR if no _guards were used:

var hashids = new HashidsNet.Hashids("salt", minHashLength: 4);

var hash = hashids.Encode(123);
Console.WriteLine(hash);

var decoded = hashids.DecodeSingle(hash); // <-- Exception here
Console.WriteLine(decoded);

@jetersen this still throws with minHashLength=5

jetersen · 2022-04-04T07:49:38Z

Damn empty entries 🤣🤣🤣🤣

jetersen · 2022-04-04T20:26:00Z

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19044.1620 (21H2)
AMD Ryzen 9 3950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=6.0.103
  [Host]     : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT
  Job-AEAOHU : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT

OutlierMode=DontRemove  Runtime=.NET 6.0  MemoryRandomization=True

The slight speed difference I think is only down to outliers... Which is set to not remove 🤔

Before: a7478cd

|               Method |       Mean |    Error |   StdDev | Code Size |  Gen 0 | Allocated |
|--------------------- |-----------:|---------:|---------:|----------:|-------:|----------:|
|        RoundtripInts | 3,785.7 ns | 18.53 ns | 17.33 ns |      50 B | 0.0610 |     512 B |
|       RoundtripLongs | 4,287.0 ns | 18.31 ns | 17.13 ns |   3,330 B | 0.0610 |     512 B |
|         RoundtripHex | 3,725.4 ns | 22.88 ns | 21.41 ns |      49 B | 0.1602 |   1,344 B |
|         SingleNumber |   844.0 ns |  3.69 ns |  3.45 ns |     145 B | 0.0076 |      64 B |
|        DecodeNumbers |   862.9 ns |  4.09 ns |  3.82 ns |   1,359 B | 0.0181 |     152 B |
|      RoundtripSingle | 1,255.6 ns |  8.97 ns |  8.39 ns |     304 B | 0.0076 |      64 B |
| SingleNumberAsParams |   862.7 ns |  4.93 ns |  4.61 ns |   2,040 B | 0.0191 |     160 B |

After: a7478cd

|               Method |       Mean |    Error |   StdDev | Code Size |  Gen 0 | Allocated |
|--------------------- |-----------:|---------:|---------:|----------:|-------:|----------:|
|        RoundtripInts | 3,827.1 ns | 25.90 ns | 24.22 ns |      50 B | 0.0305 |     264 B |
|       RoundtripLongs | 4,356.8 ns | 34.19 ns | 31.98 ns |   3,612 B | 0.0229 |     224 B |
|         RoundtripHex | 3,817.9 ns | 13.13 ns | 12.28 ns |      49 B | 0.1335 |   1,128 B |
|         SingleNumber |   846.4 ns |  5.44 ns |  5.09 ns |     145 B | 0.0076 |      64 B |
|        DecodeNumbers |   864.6 ns |  3.67 ns |  3.43 ns |   1,641 B | 0.0076 |      64 B |
|      RoundtripSingle | 1,248.2 ns |  7.87 ns |  7.36 ns |     304 B | 0.0076 |      64 B |
| SingleNumberAsParams |   855.6 ns |  3.93 ns |  3.67 ns |   2,040 B | 0.0191 |     160 B |

KeterSCP · 2022-04-04T21:48:46Z

Hmm, the following code produces different exception for main and PR branches:

var hashids = new HashidsNet.Hashids("salt", minHashLength: 0, alphabet: "0123456789ABCDEF");

var hash = hashids.EncodeLong(long.MaxValue);
Console.WriteLine(hash);

var decoded = hashids.DecodeSingleLong(hash + "1"); // HashidsNet.NoResultException on main branch and HashidsNet.MultipleResultsException on PR branch
Console.WriteLine(decoded);

jetersen · 2022-04-05T06:54:55Z

@KeterSCP That's true because I decided to check for separators ahead of time. Previous code was doing after the decode had returned multiple numbers.

So that's a toss up and this behavior was only added in 1.5.0 so which behavior is more correct?

See #57

KeterSCP · 2022-04-05T07:12:33Z

@KeterSCP That's true because I decided to check for separators ahead of time. Previous code was doing after the decode had returned multiple numbers.

So that's a toss up and this behavior was only added in 1.5.0 so which behavior is more correct?

See #57

I've checked the 1.4.1 version and following sample produces array of 0 length:

var hashids = new HashidsNet.Hashids("salt", minHashLength: 0, alphabet: "0123456789ABCDEF");

var hash = hashids.EncodeLong(1000);
Console.WriteLine(hash);

var decodedArray = hashids.DecodeLong(hash + "1");
Console.WriteLine(decodedArray.Length); // <-- 0 (No results decoded)

While on the PR branch this gives a MultipleResultsException.
Generally speaking, I support such perf changes as long as they mirror old behavior, otherwise, it would introduce a breaking change.

manigandham · 2022-04-05T08:16:50Z

@jetersen

Can you please rebase on master to use the latest tests?

Also agree with @KeterSCP that the behavior shouldn't change. If there are no results decoded then it should not be returning a MultipleEntries exception. Is your code finding multiple integers in that hash?

jetersen · 2022-04-05T08:24:16Z

I took your example @KeterSCP

You specifically added a 1 to decode and with your setup that is one of the separators:

So how can DecodeSingle be wrong?

I can remove the check for separators but than I should also remove the MultipleEntriesException cause there is no way to detect other than to look for separators after the result does not match the GenerateHashFrom equals check.

I tried to keep the behavior of DecodeSingleLong as it was coded in 1.5.0:

hashids.net/src/Hashids.net/Hashids.cs

Lines 180 to 181 in b2c7877

    
           if (numbers.Length > 1) 
        
               throw new MultipleResultsException("The hash provided yielded more than one result.");

jetersen · 2022-04-05T08:25:30Z

Rebased

manigandham · 2022-04-05T08:30:15Z

Rebased

The log doesn't show the changes. You might need to pull down the changes on master first before rebasing...

Signed-off-by: Joseph Petersen <josephp90@gmail.com>

jetersen · 2022-04-05T08:41:44Z

Rebased successfully 😅 I forgot to fetch upstream before rebasing.

KeterSCP · 2022-04-05T08:53:08Z

I took your example @KeterSCP

You specifically added a 1 to decode and with your setup that is one of the separators:

So how can DecodeSingle be wrong?

I can remove the check for separators but than I should also remove the MultipleEntriesException cause there is no way to detect other than to look for separators after the result does not match the GenerateHashFrom equals check.

I tried to keep the behavior of DecodeSingleLong as it was coded in 1.5.0:

hashids.net/src/Hashids.net/Hashids.cs

Lines 180 to 181 in b2c7877

if (numbers.Length > 1)

throw new MultipleResultsException("The hash provided yielded more than one result.");

Well, I just checked how it behaves for invalid hashes and compared how it did before. If such change is ok for the author of library, then i suppose it can be merged. Code looks good.
cc: @ullmark

As this can never happen without checking for separators.

jetersen · 2022-04-05T08:55:19Z

I created 535df3d as another way. This would result in NoResultException when trying to parse multiple when using DecodeSingle

I can remove the commit as well.

I have added my reasons for the PRs in the description.

src/Hashids.net/Hashids.cs

jetersen · 2022-04-08T14:12:19Z

src/Hashids.net/Hashids.cs

+            return Array.Empty<long>();
+        }
+
+        private long[] NumbersFrom(string hash)


Created this new method to reset stack and avoid stackoverflow 😅

jetersen · 2022-04-08T14:13:27Z

Before:

|               Method |       Mean |    Error |   StdDev | Code Size |  Gen 0 | Allocated |
|--------------------- |-----------:|---------:|---------:|----------:|-------:|----------:|
|        RoundtripInts | 3,785.7 ns | 18.53 ns | 17.33 ns |      50 B | 0.0610 |     512 B |
|       RoundtripLongs | 4,287.0 ns | 18.31 ns | 17.13 ns |   3,330 B | 0.0610 |     512 B |
|         RoundtripHex | 3,725.4 ns | 22.88 ns | 21.41 ns |      49 B | 0.1602 |   1,344 B |
|         SingleNumber |   844.0 ns |  3.69 ns |  3.45 ns |     145 B | 0.0076 |      64 B |
|        DecodeNumbers |   862.9 ns |  4.09 ns |  3.82 ns |   1,359 B | 0.0181 |     152 B |
|      RoundtripSingle | 1,255.6 ns |  8.97 ns |  8.39 ns |     304 B | 0.0076 |      64 B |
| SingleNumberAsParams |   862.7 ns |  4.93 ns |  4.61 ns |   2,040 B | 0.0191 |     160 B |

After 99a41e4, 395a2d6 and 7567d90:

|               Method |       Mean |    Error |   StdDev |  Gen 0 | Code Size | Allocated |
|--------------------- |-----------:|---------:|---------:|-------:|----------:|----------:|
|        RoundtripInts | 3,835.8 ns | 11.98 ns | 11.21 ns | 0.0229 |      50 B |     200 B |
|       RoundtripLongs | 4,389.7 ns | 16.26 ns | 15.21 ns | 0.0153 |     862 B |     136 B |
|         RoundtripHex | 3,843.8 ns |  9.92 ns |  9.28 ns | 0.1259 |      49 B |   1,064 B |
|         SingleNumber |   875.7 ns |  1.76 ns |  1.65 ns | 0.0076 |     196 B |      64 B |
|        DecodeNumbers |   875.4 ns |  8.87 ns |  8.30 ns | 0.0038 |     501 B |      32 B |
|   DecodeSingleNumber |   814.0 ns |  2.66 ns |  2.49 ns |      - |     118 B |         - |
|      RoundtripSingle | 1,272.6 ns | 12.14 ns | 11.36 ns | 0.0038 |     283 B |      32 B |
| SingleNumberAsParams |   911.1 ns |  4.11 ns |  3.84 ns | 0.0191 |     450 B |     160 B |

I would like to see if it possible to get them to return ReadOnlySpan<char> to have return option that is only on the stack.

But GenerateHashFrom now allows us to potentially do that.

KeterSCP · 2022-04-08T17:09:01Z

src/Hashids.net/Hashids.cs

-        public string EncodeLong(long number) => GenerateHashFrom(stackalloc[] { number });
+        public string EncodeLong(long number)
+        {
+            Span<char> result = stackalloc char[20];


Why there is a limit of 20 chars? Now it throws if you try to encode value with minHashLength parameter set to >20, however previously it was possible to get string of any length

I thought the max length for a long was 19 plus 1 for lottery hence 20.

We should have a test that validate any length.

Also potentially any length does not make sense when it comes to max url length or other serialization issues or memory optimization.

Don't confuse input number length (e.g var num = 1234 has length of 4) and output hash length (which can differ)

manigandham · 2022-05-19T06:57:31Z

hey @jetersen

The fundamental problem here is that DecodeSingle is still not truthful about the error. Previously it would return MultipleResultsException even if there was nothing decoded, but now the code never returns MultipleResultsException even if there are, effectively pointing users to the wrong error.

As nice as it is to have improved performance, I don't think it should come at the cost of correct results. Is there a way to fix this?

jetersen · 2022-05-19T07:05:55Z

@manigandham As you can see there was an argument about this

Whether it returns NoResultException or MultipleEntriesException to me is irrelevant.

But as you can see I suggest I can revert that change in 535df3d

Before 535df3d it is possible to detect multiple entries but apparently the way I do that was not appreciated.

I was looking for any Separator characters, and throw MultipleEntriesException, see #65 (comment) and see #65 (comment)

Again MultipleEntriesException was only added in recent version as well. So in my opinion we could do either.
Revert 535df3d to throw MultipleEntriesException or keep 535df3d thereby throwing NoResultException

What difference does it make MultipleEntriesException is the same as NoResultException both exception is a non result situation.

manigandham · 2022-05-21T17:35:39Z

What difference does it make MultipleEntriesException is the same as NoResultException both exception is a non result situation.

An exception being thrown signals that there's an issue with the operation, but the actual exception type describes why there was an issue. I think it's very important for the user to know so they understand why the result didn't decode (whether there's multiple numbers or none).

I'll leave it to @ullmark to decide how to proceed.

ullmark · 2022-05-22T20:36:13Z

@manigandham If the performance increases of this library is important for the ones who uses it, and this looks good we should merge this.

tbh; it uses some syntax I've never seen or used (or had any need to) in C#, so @jetersen you are welcome to come in and maintain if you like. :)

Re. the errors, if it's not possible to detect multiple entries in a good way, just throw a "NoResultException" since that is still true, given the alphabet + salt, and how you use the library, we weren't able to get a result. 🤷‍♂️

manigandham · 2022-05-22T20:44:29Z

@jetersen if you want to change the exception to say NoResultException then I'll merge in and do the next release.

jetersen · 2022-05-22T20:58:43Z

@manigandham it is already throwing NoResultException, see the tests in GeneralTests.cs :)

jetersen · 2022-05-22T21:05:12Z

@ullmark I would be happy to help maintain and review PRs 😄

manigandham · 2022-05-22T22:29:10Z

v1.6.0 released https://www.nuget.org/packages/Hashids.net/1.6.0

jetersen added 5 commits April 5, 2022 10:41

reduce amount allocation for single number decode

d4278eb

Signed-off-by: Joseph Petersen <josephp90@gmail.com>

fix issue with guarded ids

b76079e

add optimized splitter

597975f

Make split private

adca5be

use splitter for multiple numbers

99a41e4

Remove MultipleResultsException

535df3d

As this can never happen without checking for separators.

Berezhnyk reviewed Apr 7, 2022

View reviewed changes

src/Hashids.net/Hashids.cs Outdated Show resolved Hide resolved

jetersen added 2 commits April 7, 2022 14:38

fix if condition check for number

2be6ee2

allocation free GenerateHashFrom

395a2d6

jetersen commented Apr 8, 2022

View reviewed changes

src/Hashids.net/Hashids.cs Show resolved Hide resolved

Reduce allocation further for Encode

7567d90

jetersen commented Apr 8, 2022

View reviewed changes

fix return empty string

aac4744

KeterSCP reviewed Apr 8, 2022

View reviewed changes

fix number length

f8b4a59

jetersen mentioned this pull request Apr 27, 2022

Improve performance & memory allocation #69

Closed

Remove reference to multiple results exception

6af0035

manigandham approved these changes May 22, 2022

View reviewed changes

manigandham merged commit 480cabe into ullmark:master May 22, 2022

manigandham self-assigned this May 22, 2022

jetersen deleted the feat/improveSingleDecode branch May 22, 2022 21:33

jetersen mentioned this pull request Aug 8, 2022

Attempting to Decode short strings results in incorrect exceptions being produced #75

Closed

reduce amount allocation for single number decode #65

reduce amount allocation for single number decode #65

Uh oh!

Conversation

jetersen commented Apr 3, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jetersen commented Apr 3, 2022

Uh oh!

KeterSCP commented Apr 4, 2022

Uh oh!

jetersen commented Apr 4, 2022

Uh oh!

jetersen commented Apr 4, 2022

Uh oh!

jetersen commented Apr 4, 2022

Uh oh!

KeterSCP commented Apr 4, 2022

Uh oh!

jetersen commented Apr 4, 2022

Uh oh!

jetersen commented Apr 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KeterSCP commented Apr 4, 2022

Uh oh!

jetersen commented Apr 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KeterSCP commented Apr 5, 2022

Uh oh!

manigandham commented Apr 5, 2022

Uh oh!

jetersen commented Apr 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jetersen commented Apr 5, 2022

Uh oh!

manigandham commented Apr 5, 2022

Uh oh!

jetersen commented Apr 5, 2022

Uh oh!

KeterSCP commented Apr 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jetersen commented Apr 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jetersen Apr 8, 2022

Choose a reason for hiding this comment

Uh oh!

jetersen commented Apr 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KeterSCP Apr 8, 2022

Choose a reason for hiding this comment

Uh oh!

jetersen Apr 8, 2022

Choose a reason for hiding this comment

Uh oh!

jetersen Apr 8, 2022

Choose a reason for hiding this comment

Uh oh!

KeterSCP Apr 8, 2022

Choose a reason for hiding this comment

Uh oh!

manigandham commented May 19, 2022

Uh oh!

jetersen commented May 19, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

manigandham commented May 21, 2022

Uh oh!

ullmark commented May 22, 2022

Uh oh!

manigandham commented May 22, 2022

Uh oh!

jetersen commented May 22, 2022

jetersen commented Apr 3, 2022 •

edited

Loading

jetersen commented Apr 4, 2022 •

edited

Loading

jetersen commented Apr 5, 2022 •

edited

Loading

jetersen commented Apr 5, 2022 •

edited

Loading

KeterSCP commented Apr 5, 2022 •

edited

Loading

jetersen commented Apr 5, 2022 •

edited

Loading

jetersen commented Apr 8, 2022 •

edited

Loading

jetersen commented May 19, 2022 •

edited

Loading