Geekly Articles each Day
📜 ⬆️ ⬇️

[DotNetBook] Span: new .NET data type

With this article, I continue to publish a whole series of articles, the result of which will be a book on the work of the .NET CLR, and .NET as a whole (about 200 pages of the book are ready, so welcome to the end of the article for links).


Both the language and the platform have existed for many years: all this time there have been many means for working with unmanaged code. So why now comes the next API to work with unmanaged code if in fact it has existed for many, many years? In order to answer this question, it is enough to understand what we lacked before.


Developers of the platform have tried to help us brighten up everyday development using unmanaged resources: these are automatic wrappers for imported methods. And marshalling, which in most cases works automatically. It is also a stackallloc instruction, which is referred to in the chapter on the stack stack. However, as for me, if early developers using C # came from the world of C ++ (as I did), now they come from higher-level languages ​​(for example, I know a developer who came from JavaScript). And what does it mean? This means that people are becoming more and more suspicious of uncontrollable resources and constructions that are close in spirit to C / C ++ and even more so to Assembly language.


The article, though large, is an introduction to the topic Span <T> and Memory <T>

Note


The chapter published on Habré is not updated and it is possible that it is already somewhat outdated. So, please ask for a more recent text to the original:



As a result of such an attitude, there is less and less content of unsafe code in projects and more and more confidence in the API of the platform itself. This is easily verified if you look for the use of the stackalloc construct on open repositories: it is negligible. But if you take any code that uses it:


Interop.ReadDir class
/src/mscorlib/shared/Interop/Unix/System.Native/Interop.ReadDir.cs


 unsafe { // s_readBufferSize is zero when the native implementation does not support reading into a buffer. byte* buffer = stackalloc byte[s_readBufferSize]; InternalDirectoryEntry temp; int ret = ReadDirR(dir.DangerousGetHandle(), buffer, s_readBufferSize, out temp); // We copy data into DirectoryEntry to ensure there are no dangling references. outputEntry = ret == 0 ? new DirectoryEntry() { InodeName = GetDirectoryEntryName(temp), InodeType = temp.InodeType } : default(DirectoryEntry); return ret; }

It becomes clear the reason for the unpopularity. Look without reading the code and answer one question for yourself: do you trust him? I can assume that the answer is no. Then answer the other: why? The answer will be obvious: besides the fact that we see the word Dangerous , which somehow hints that something can go wrong, the second factor affecting our attitude is the line byte* buffer = stackalloc byte[s_readBufferSize]; more specifically, byte* . This record is a trigger for anyone to have a thought in their head: “what else couldn’t it be possible to do something else?”. Then let's understand psychoanalysis a little bit more: why can a similar idea arise? On the one hand, we use the constructs of the language and the syntax proposed here is far from, for example, C ++ / CLI, which allows you to do anything at all (including inserts on a pure Assembler), and on the other, it looks unusual.


So what is the question? How to get developers back into the fold of unmanaged code? It is necessary to give them a sense of calm that they cannot make a mistake by chance, out of ignorance. So, what Span<T> and Memory<T> Span<T> introduced for?


Span [T], ReadOnlySpan [T]


The Span type represents a part of a certain data array, a subrange of its values. At the same time, allowing, as in the case of an array, to work with elements of this range for both writing and reading. However, let us, for overclocking and general understanding, compare the types of data for which the implementation of the Span type was made and look at the possible goals of its introduction.


The first data type you want to talk about is a regular array. For arrays, working with Span will look like this:


  var array = new [] {1,2,3,4,5,6}; var span = new Span<int>(array, 1, 3); var position = span.BinarySearch(3); Console.WriteLine(span[position]); // -> 3

As we can see in this example, for a start we create a certain array of data. After that we create a Span (or a subset), which, referring to the array itself, allows it to the access code only access that range of values ​​that was specified during initialization.


Here we see the first property of this data type: this is the creation of some context. Let's develop our idea with contexts:


 void Main() { var array = new [] {'1','2','3','4','5','6'}; var span = new Span<char>(array, 1, 3); if(TryParseInt32(span, out var res)) { Console.WriteLine(res); } else { Console.WriteLine("Failed to parse"); } } public bool TryParseInt32(Span<char> input, out int result) { result = 0; for (int i = 0; i < input.Length; i++) { if(input[i] < '0' || input[i] > '9') return false; result = result * 10 + ((int)input[i] - '0'); } return true; } ----- 234

As we can see, Span<T> introduces an abstraction of access to a certain section of memory for both reading and writing. What does this give us? If we recall, on the basis of what else Span can be made, then we recall both unmanaged resources and lines:


 // Managed array var array = new[] { '1', '2', '3', '4', '5', '6' }; var arrSpan = new Span<char>(array, 1, 3); if (TryParseInt32(arrSpan, out var res1)) { Console.WriteLine(res1); } // String var srcString = "123456"; var strSpan = srcString.AsSpan().Slice(1, 3); if (TryParseInt32(strSpan, out var res2)) { Console.WriteLine(res2); } // void * Span<char> buf = stackalloc char[6]; buf[0] = '1'; buf[1] = '2'; buf[2] = '3'; buf[3] = '4'; buf[4] = '5'; buf[5] = '6'; if (TryParseInt32(buf.Slice(1, 3), out var res3)) { Console.WriteLine(res3); } ----- 234 234 234

That is, it turns out that Span<T> is a unification tool for working with memory: managed and unmanaged, which guarantees safety in working with this kind of data during the Garbage Collection: if the sections of memory with controlled arrays move, then for it will be safe for us.


However, is it worth it so much joy? Was it possible to achieve all this before? For example, if we talk about managed arrays, then there is even no doubt: just wrap the array in another class, providing a similar interface and everything is ready. Moreover, a similar operation can be done with strings: they have the necessary methods. Again, just wrap the string in the exact same type and provide methods for working with it. Another thing is that in order to store a string, buffer or array in one type, you will have to tinker strongly, storing references to each of the possible options in a single copy (of course, there will be only one active):


 public readonly ref struct OurSpan<T> { private T[] _array; private string _str; private T * _buffer; // ... }

Or if to make a start from architecture, then to do three types inheriting the uniform interface. It turns out that in order to make a single interface tool between these managed data types, while maintaining maximum performance, a path other than Span<T> does not exist.


Further, if we continue the reasoning, what is a ref struct in terms of Span ? These are the very “structures, they are only on the stack,” which we so often hear about at interviews. This means that this data type can only go through the stack and has no right to go to the heap. That is why Span , being a ref structure, is a context data type that ensures the operation of methods, but not objects in memory. From this for his understanding and it is necessary to make a start.


From here we can formulate the definition of the type Span and the readonly type associated with it of type ReadOnlySpan:


Span is a data type that provides a single interface for working with heterogeneous types of data arrays, as well as the ability to transfer a subset of this array to another method so that regardless of the context depth, the access speed to the original array is constant and as high as possible.

And really: if we have something like this:


 public void Method1(Span<byte> buffer) { buffer[0] = 0; Method2(buffer.Slice(1,2)); } Method2(Span<byte> buffer) { buffer[0] = 0; Method3(buffer.Slice(1,1)); } Method3(Span<byte> buffer) { buffer[0] = 0; }

then the speed of access to the source buffer will be as high as possible: you are not working with a managed object, but with a managed pointer. Those. not with the .NET managed type, but with an unsafe type enclosed in a managed shell.


Span [T] on examples


The person is so arranged that often until he gets a certain experience, then the final understanding for which the necessary tool often does not come. Therefore, since we need some experience, let's turn to examples.


ValueStringBuilder


One of the most algorithmically interesting examples is the ValueStringBuilder type, which is prikopan somewhere in the depths of mscorlib and for some reason, like many other interesting data types, is marked with the internal modifier, which means that if you didn’t study the source code mscorlib, we would would never know.


What is the main disadvantage of the StringBuilder system type? This is of course its essence: both he himself and what he is based on (and this is an array of char[] characters) are reference types. And this means at least two things: we still (albeit slightly) load a bunch and the second - we increase the odds of a miss in the processor caches.


Another question that I had to StringBuilder - is the formation of small strings. Those. when the resulting string "give a tooth" is short: for example, less than 100 characters. When we have sufficiently short formatting, performance raises questions:


  $"{x} is in range [{min};{max}]"

How much worse is this record than manual shaping via StringBuilder? The answer is far from always obvious: everything strongly depends on the place of formation: how often this method will be called. After all, first string.Format allocates memory for an internal StringBuilder , which will create an array of characters (SourceString.Length + args.Length * 8) and if during the formation of the array it turns out that the length was not guessed, then another StringBuilder will be created to form the continuation, thus forming a single-linked list. As a result, it will be necessary to return the generated string: this is another copy. Tranquility and waste. Now, if we could get rid of placing the first string in the heap of the first array, it would be great: we would definitely get rid of one problem.


Take a look at the type from the depths of mscorlib :


Class ValueStringBuilder
/ src / mscorlib / shared / System / Text / ValueStringBuilder


  internal ref struct ValueStringBuilder { //           private char[] _arrayToReturnToPool; //     private Span<char> _chars; private int _pos; //    ,       public ValueStringBuilder(Span<char> initialBuffer) { _arrayToReturnToPool = null; _chars = initialBuffer; _pos = 0; } public int Length { get => _pos; set { int delta = value - _pos; if (delta > 0) { Append('\0', delta); } else { _pos = value; } } } //   -       public override string ToString() { var s = new string(_chars.Slice(0, _pos)); Clear(); return s; } //       //     :   public void Insert(int index, char value, int count) { if (_pos > _chars.Length - count) { Grow(count); } int remaining = _pos - index; _chars.Slice(index, remaining).CopyTo(_chars.Slice(index + count)); _chars.Slice(index, count).Fill(value); _pos += count; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Append(char c) { int pos = _pos; if (pos < _chars.Length) { _chars[pos] = c; _pos = pos + 1; } else { GrowAndAppend(c); } } [MethodImpl(MethodImplOptions.NoInlining)] private void GrowAndAppend(char c) { Grow(1); Append(c); } //   ,     //         //            //           [MethodImpl(MethodImplOptions.NoInlining)] private void Grow(int requiredAdditionalCapacity) { Debug.Assert(requiredAdditionalCapacity > _chars.Length - _pos); char[] poolArray = ArrayPool<char>.Shared.Rent(Math.Max(_pos + requiredAdditionalCapacity, _chars.Length * 2)); _chars.CopyTo(poolArray); char[] toReturn = _arrayToReturnToPool; _chars = _arrayToReturnToPool = poolArray; if (toReturn != null) { ArrayPool<char>.Shared.Return(toReturn); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] private void Clear() { char[] toReturn = _arrayToReturnToPool; this = default; // for safety, to avoid using pooled array if this instance is erroneously appended to again if (toReturn != null) { ArrayPool<char>.Shared.Return(toReturn); } } //  :       private void AppendSlow(string s); public bool TryCopyTo(Span<char> destination, out int charsWritten); public void Append(string s); public void Append(char c, int count); public unsafe void Append(char* value, int length); public Span<char> AppendSpan(int length); }

This class is similar in functionality to its older brother, StringBuilder , while possessing one interesting and very important feature: it is a significant type. Those. stored and transmitted entirely by value. And the newest modifier type ref , which is assigned to the type declaration signature, tells us that this type has an additional limitation: it has the right to be only on the stack. Those. outputting its instructions in the class fields will result in an error. Why all these squats? To answer this question, just look at the StringBuilder class, the essence of which we have just described:


Class StringBuilder /src/mscorlib/src/System/Text/StringBuilder.cs


 public sealed class StringBuilder : ISerializable { // A StringBuilder is internally represented as a linked list of blocks each of which holds // a chunk of the string. It turns out string as a whole can also be represented as just a chunk, // so that is what we do. internal char[] m_ChunkChars; // The characters in this block internal StringBuilder m_ChunkPrevious; // Link to the block logically before this block internal int m_ChunkLength; // The index in m_ChunkChars that represent the end of the block internal int m_ChunkOffset; // The logical offset (sum of all characters in previous blocks) internal int m_MaxCapacity = 0; // ... internal const int DefaultCapacity = 16;

StringBuilder is a class within which there is a reference to an array of characters. Those. when you create it, then at least two objects are created: a StringBuilder itself and an array of characters of at least 16 characters (by the way, this is why it is so important to set the expected length of the string: its construction will go through the generation of a simply connected list of 16-character arrays. Agree, waste ). What does this mean in the context of our conversation about the type ValueStringBuilder: by default is absent, since it borrows memory from the outside, plus it itself is a significant type and forces the user to place a buffer for characters on the stack. As a result, the entire instance of the type is placed on the stack along with its contents, and the question of optimization here becomes resolved. No heap allocation? No problem with subsidence performance. But you tell me: why then do not use ValueStringBuilder (or its self-written version: it’s internal itself and is not available to us) always? The answer is this: you have to look at the problem that you are solving. Will the resulting string be of known size? Will she have some known maximum length? If the answer is "yes" and if the size of the string does not exceed some reasonable limits, then you can use a meaningful version of StringBuilder. Otherwise, if we expect long lines, we switch to using the regular version.


ValueListBuilder


The second data type, which I would especially like to note, is the ValueListBuilder type. It was created for situations where it is necessary for a short time to create a certain collection of elements and immediately give it to the processing of some algorithm.


Agree: the task is very similar to the ValueStringBuilder task. Yes, and it is solved in a very similar way:


ValueListBuilder.cs file


Speaking directly, such situations are quite frequent. However, earlier we solved this question in another way: we created a List , filled it with data and lost the link. If the method is called often enough, a sad situation arises: many instances of the List class hang in the heap, and along with them the arrays associated with them hang in the heap. Now this problem is solved: no additional objects will be created. However, as in the case of ValueStringBuilder , it is solved only for Microsoft programmers: the class has the modifier internal .


Rules and practice of use


In order to finally understand the essence of a new data type, it is necessary to “play around” with it by writing a couple of, or better, more methods that use it. However, the basic rules can be learned now:



In other cases, it is worth looking at either Memory or using classic data types.


How Span Works


Additionally, I would like to talk about how Span works and what is so remarkable about it. And there is something to talk about: the data type itself is divided into two versions: for .NET Core 2.0+ and for all others.


File Span.Fast.cs, .NET Core 2.0


 public readonly ref partial struct Span<T> { ///    .NET    internal readonly ByReference<T> _pointer; ///      private readonly int _length; // ... }

File ??? [decompiled]


 public ref readonly struct Span<T> { private readonly System.Pinnable<T> _pinnable; private readonly IntPtr _byteOffset; private readonly int _length; // ... }

The thing is that the large .NET Framework and .NET Core 1. * do not have a specially modified garbage collector (unlike the version of .NET Core 2.0+) and therefore have to drag along an additional pointer: to the beginning of the buffer with which Job. That is, it turns out that Span internally works with managed objects of the .NET platform as unmanaged. Look at the insides of the second variant of the structure: there are three fields there. The first field is a link to the managed object. The second is the offset from the beginning of this object in bytes to get the beginning of the data buffer (in rows this is a buffer with char characters, in arrays it is a buffer with data of an array). And, finally, the third field - the number of items laid one after another of this buffer.


For example, take the Span job for strings:


Coreclr :: src / System.Private.CoreLib / shared / System / MemoryExtensions.Fast.cs file


 public static ReadOnlySpan<char> AsSpan(this string text) { if (text == null) return default; return new ReadOnlySpan<char>(ref text.GetRawStringData(), text.Length); }

Where string.GetRawStringData() looks like this:


Coreclr :: src / System.Private.CoreLib / src / System / String.CoreCLR.cs field definition file


GetRawStringData definition file coreclr :: src / System.Private.CoreLib / shared / System / String.cs


 public sealed partial class String : IComparable, IEnumerable, IConvertible, IEnumerable<char>, IComparable<string>, IEquatable<string>, ICloneable { // // These fields map directly onto the fields in an EE StringObject. See object.h for the layout. // [NonSerialized] private int _stringLength; // For empty strings, this will be '\0' since // strings are both null-terminated and length prefixed [NonSerialized] private char _firstChar; internal ref char GetRawStringData() => ref _firstChar; }

Those. it turns out that the method climbs directly into the line, and the ref char specification allows you to track the GC unmanaged link inside the line, moving it along with the line during the GC response.


The same story happens with arrays: when Span is created, some code inside the JIT calculates the offset of the beginning of the array data and initializes Span this offset. And how to calculate the displacements for strings and arrays, we learned in the chapter about the structure of objects in memory.


Span [T] as return value


, Span , , . :


 unsafe void Main() { var x = GetSpan(); } public Span<byte> GetSpan() { Span<byte> reff = new byte[100]; return reff; }

. , :


 unsafe void Main() { var x = GetSpan(); } public Span<byte> GetSpan() { Span<byte> reff = stackalloc byte[100]; return reff; }

. , , , .


, , , , . , . , , , x[0.99] .


, , , , : CS8352 Cannot use local 'reff' in this context because it may expose referenced variables outside of their declaration scope : , , , .



Span<T> , . , use cases .


Link to the whole book




')

Source: https://habr.com/ru/post/418911/

More articles:


All Articles