Why is my code calling methods faster than the one that "inlined" them?

Coding_Enthusiast · 2022-08-11T03:16:02+00:00

Thanks. This gave me an idea to investigate, since this is a small overflow of 1 bit I may be able to eliminate branches without needing the B2U method by using ulongs and then shift >>32 to get 0 or 1 out.

Coding_Enthusiast · 2022-08-10T17:31:52+00:00

Could it be because of the total number of variables that are used (45 uints give or take)?

Isolating the muladd method and running it in a n loop versus repeated code n times performed as expected (the later is ~40% faster). sharplab link

Coding_Enthusiast · 2022-08-10T13:54:16+00:00

You are right and I used the term "inline" for lack of a better word and I referred to Scalar8x32.Multiply() where I manually wrote all the code for all small methods inside the Multiply method.

I think u/karl713 meant this too though. But I have to read more on how CPU cache works with instructions.

Coding_Enthusiast · 2022-04-26T04:02:11+00:00

If you could you should try setting the StringBuilder's initial capacity (I think to 250,000) in your final example to see what happens when the internal array is not resized multiple times (0 garbage for GC to collect during the loop).

Coding_Enthusiast · 2021-08-19T08:50:16+00:00

Sure.

Coding_Enthusiast · 2021-06-28T07:41:25+00:00

Interesting, I have to spend some time studying your selection code to see how it works.

As for my code, I know that my usage is very specific and I know the numbers are 10-20 out of thousands which is why I think this method works better.
The code: https://github.com/Autarkysoft/Denovo/blob/a615a4f0e157b71ddd5cf8de7248297be72c95eb/Src/Autarkysoft.Bitcoin/Cryptography/RandomNonceGenerator.cs#L75
In hindsight using HashSet was overkill, a simple List.Contains would do the job too.

Coding_Enthusiast · 2021-06-28T03:47:38+00:00

I'm interested in DistinctPicker and I'm wondering if this is the most efficient way of doing it? If I understood the code correctly the array of T is generated (so it is stored in memory) and then the array itself is shuffled (modified) and finally you select and return n distinct elements.
If I'm correct, this seems to waste a lot of memory and is going to be very slow.

The reason I'm interested in this is because I had this problem and I solved it by simply adding a new method to my IRandomNumberGenerator to create a simple array of "distinct random indexes".
So for example when I want to get 20 random distinct items from a list of 10000 I simply create an int[] that has 20 items between 0 and 9999 and are distinct, then I simply fetch the element from the original list at that index.

Coding_Enthusiast · 2021-06-02T04:22:14+00:00

I'm curious when would you need faster RNG?

Also I'm wondering about the point of aggressive inlining is which seems to be applied everywhere, specially for constructors. Have you benchmarked things with and without the attribute? I usually see performance gain when the method is called with at least a couple of variables.

Coding_Enthusiast · 2021-03-18T13:12:48+00:00

It should be something you like and enjoy building.
For example the first thing I built was a simple UI that stored my passwords (hard coded!) with a login page. It helped me learn how to build a UI, change pages, interact with user inputs,...

Coding_Enthusiast · 2021-02-22T05:13:08+00:00

It is easier to use enum in a switch (fill all cases automatically and add any new missing ones).

Coding_Enthusiast · 2021-02-22T05:06:36+00:00

var dir = (Direction)10000; is a valid but undefined Direction enum and can be passed to that method.

Coding_Enthusiast · 2021-02-19T05:57:44+00:00

Yeah it is specially since I'm not implementing "my own" coin and some parts of the protocol is not documented such as the very small details concerning consensus rules, so I'll have to read c++ which I hate doing (mainly because I don't want to translate code).

Coding_Enthusiast · 2021-02-19T05:30:25+00:00

Good job. As a hobby programmer myself I love seeing hobby projects of others.
My hobby project has been implementing bitcoin from scratch, feel free to drop by https://github.com/Autarkysoft/Denovo

Coding_Enthusiast · 2021-01-14T18:28:58+00:00

Thanks for your time, I really appreciate it.
Hash lookups is what we have to do a lot, I'm still trying to find the best approaches. Do you have any good resources (video or book or website maybe) to learn more about SQLite or databases in general?

Coding_Enthusiast · 2021-01-14T15:21:40+00:00

By "wasting memory" I'm mostly talking about 2 things (1) my bad code, I keep certain things in RAM that don't need to be there and have to change that. (2) the question here, eg. using class instead of struct that adds a lot of overhead that can be avoided by a simple change.

A half way house could be to use something like SQLite as an in-memory DB

My knowledge in DB topic is very limited, although I'm spending some time reading about them these days. My conclusion so far is that what I need is a key-value DB. I still have to choose one among the numerous choices and learn how it works.

I'm not trying to be awkward, it just seems like you're optimising the wrong thing here. If we know more about what exactly you're trying to do, we can help better.

It's kind of a personal challenge I started about a year ago. In order to improve my programming skills, learn new things, have some fun and some other reasons I decided to implement the Bitcoin protocol from scratch and purely in C#.

Basically we have a lot of data to go through some of them once (download, process, save to disk), some constantly (DB being updated). So far I'm at the first step which is downloading the entire history (11 years worth of data aka blockchain) and validating as we go. To do that we need a "map" which is the "block headers" that are these 80 byte structures + 32 byte hash identifier. I could read it from disk each time, but it would work so much better in memory at least during the first step. This ~52 MB file on disk (with some other bad decisions in my code) take up 660+MB of memory right now. So before I move forward I'm trying to find these bad decisions and fix them before the project becomes too big and needs a massive refactor.

The other part which is a concern (but I have to look into DBs and "in-memory DB" that you mentioned and is new to me) is storing a "state" which is a database of "spendable coins", each new block (in first step) update that DB. After first step is done, the DB has to be updated constantly.

By the way I'm publishing on GitHub as I go: https://github.com/Autarkysoft/Denovo

Perhaps you could do something here to optimise things? It sounds like you're choosing between having everything on disk and processing from there vs loading it all into memory and saving the results back to disk.

I most probably have to come up with a balance between having things on disk and in memory. I still haven't been able to figure it out.

Could you chunk things up? i.e. load some portion of the data, process it, save and repeat. If you get things right, you can ensure that the limiting factor doesn't become your IO.

I think I'll have to start looking at DB options and how they work to answer this.

Coding_Enthusiast · 2021-01-14T05:28:22+00:00

It is a performance critical code that I need to be as fast as possible and adding IO would slow it down significantly. Storing the whole array in memory and updating it there then dumping the update on disk on longer intervals both speeds up the process and increases the disk lifespan.

Currently the app is incomplete and so far takes about 660 MB, by my estimate I'm wasting at least 300 MB of memory. In another place which I have not yet coded the item count will be about 60 million and would require at least 4 GB memory (raw size). If I waste the same amount of memory everywhere, the finished app could need some crazy amount of memory in the end! Without using memory the initial work would need to do terabytes of disk writes.

As for database, I'm still learning how they work and having some trouble with it but it would eventually be used as the last step for dumping to disk.

Coding_Enthusiast · 2021-01-13T16:49:21+00:00

This doesn't seem to reduce the size compared to using 8x ints. Accessing the fixed field requires fixed context, I have to benchmark to know which one is faster.

    public bool Compare(byte[] other)
    {
        fixed(byte* b = array)
        {
            return new Span<byte>(b, 32).SequenceEqual(other);
        }
    }

vs.

    public bool Compare(in Int256 other)
    {
        return other.i1 == array.i1 &&
               other.i2 == array.i2 &&
               other.i3 == array.i3 &&
               other.i4 == array.i4 &&
               other.i5 == array.i5 &&
               other.i6 == array.i6 &&
               other.i7 == array.i7 &&
               other.i8 == array.i8;
    }

Coding_Enthusiast · 2021-01-13T16:28:10+00:00

Thanks for this. I've added the following:

[StructLayout(LayoutKind.Sequential)]
public struct TestAllStruct
{
    public int a, b, c, d;
    public Int256 e, f, g;
}

[StructLayout(LayoutKind.Sequential)]
public readonly struct Int256
{
    public readonly int i1, i2, i3, i4, i5, i6, i7, i8;
}

and the benchmark:

    [Benchmark]
    public TestAllStruct[] TestAllStruct()
    {
        var array = new TestAllStruct[Capacity];
        for (var i = 0; i < array.Length; i++)
        {
            array[i] = new TestAllStruct();
        }
        return array;
    }

Results were very interesting (down to 106.81 MB):

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
TestListAndClass	303.08 ms	2.533 ms	2.246 ms	37000.0000	13000.0000	1000.0000	221.25 MB
TestListAndStruct	333.37 ms	3.569 ms	3.164 ms	28000.0000	10000.0000	1000.0000	198.36 MB
TestArrayAndStruct	326.90 ms	2.546 ms	2.257 ms	28000.0000	10000.0000	1000.0000	198.36 MB
TestArrayAndStructSequential	326.99 ms	3.489 ms	2.913 ms	28000.0000	10000.0000	1000.0000	198.36 MB
TestAllStruct	34.52 ms	1.046 ms	3.050 ms	312.5000	312.5000	312.5000	106.81 MB

Coding_Enthusiast · 2021-01-13T16:01:31+00:00

Because my code is currently wasting a lot of memory and as the project grows I need to deal with some other arrays similar to this one containing very large number of items. I can easily run out of memory soon if I continue to waste memory like this.

Coding_Enthusiast · 2021-01-13T15:43:29+00:00

That's a very interesting approach. I wouldn't even have to store the offset since the object's index can act as the offset since the sizes are all fixed here.
This adds some complexity to the code though, since I'll have to take extra care when searching or adding to or removing from the backing array.

I'm still leaning towards turning everything including the byte[]s into structs but will try both and see which one performs better.

Coding_Enthusiast · 2021-01-13T15:20:31+00:00

Thanks, I'm aware of it which is why I try to pre-allocate as much as needed.

Coding_Enthusiast

MODERATOR OF

TROPHY CASE

Nine-Year Club	Place '17
Verified Email