SpiseMisu.Text.Dstring 0.11.23

SpiseMisu.Text.Dstring

A Danish string is a German string alike implementation for .NET, managed memory optimized.

A dstring consists of 16-bytes (128-bits) of continuous memory, where:

• The first byte, stores a bitmask for the seven next bytes as well as a byte [] pointer

• The first byte, uses a 4-bit bitmask to store the length of the dstring prefix, as well as another 4-bit bitmask to store flags for encoding-and-format. Once the upperbound length of the dstring prefix length is reached, a 3-bit bitmask with compression flags is available:

  # Upperbound length of eight (compression flags are available)
  +--------+
  |▭▭▭▭■□□□|
  +--------+
  # Lenth of five (compression flags are NOT available)
  +--------+
  |▭▭▭▭□■□■|
  +--------+
  

  and

  # Encoding. Default is multiple single-byte UTF8 for optimal storage
  +--------+
  |□□□□▭▭▭▭| UTF8.......: Encoded bytes as multiple UTF8 single-bytes
  +--------+
  |□□□■▭▭▭▭| ASCII......: Encoded bytes in [0x00 - 0x7F]
  +--------+
  |□□■□▭▭▭▭| ExtASCII...: Encoded bytes in [0x00 - 0xFF]
  +--------+
  # Encoding and Format placeholders
  +--------+
  |□□■■▭▭▭▭| PlaceholderF03 (placeholder for future formats/encodings)
  +--------+
  |□■□□▭▭▭▭| PlaceholderF04 (placeholder for future formats/encodings)
  +--------+
  |□■□■▭▭▭▭| PlaceholderF05 (placeholder for future formats/encodings)
  +--------+
  |□■■□▭▭▭▭| PlaceholderF06 (placeholder for future formats/encodings)
  +--------+
  |□■■■▭▭▭▭| PlaceholderF07 (placeholder for future formats/encodings)
  +--------+
  |■□□□▭▭▭▭| PlaceholderF08 (placeholder for future formats/encodings)
  +--------+
  |■□□■▭▭▭▭| PlaceholderF09 (placeholder for future formats/encodings)
  +--------+
  |■□■□▭▭▭▭| PlaceholderF10 (placeholder for future formats/encodings)
  +--------+
  |■□■■▭▭▭▭| PlaceholderF11 (placeholder for future formats/encodings)
  +--------+
  |■■□□▭▭▭▭| PlaceholderF12 (placeholder for future formats/encodings)
  +--------+
  |■■□■▭▭▭▭| PlaceholderF13 (placeholder for future formats/encodings)
  +--------+
  |■■■□▭▭▭▭| PlaceholderF13 (placeholder for future formats/encodings)
  +--------+
  # Format
  +--------+
  |■■■■▭▭▭▭| JSON.......: Ex: [{"foo":42}]
  +--------+
  bit-mask
  

  and

  # Default is uncompressed
  +--------+
  |▭▭▭▭■□□□| Uncompressed
  +--------+
  # Compression algorithms, with streaming support
  +--------+
  |▭▭▭▭■□□■| Deflate
  +--------+
  |▭▭▭▭■□■□| GZip
  +--------+
  |▭▭▭▭■□■■| ZLib
  +--------+
  |▭▭▭▭■■□□| Brotli
  +--------+
  # Compression algorithms placeholders
  +--------+
  |▭▭▭▭■■□■| PlaceholderF05
  +--------+
  |▭▭▭▭■■■□| PlaceholderF06
  +--------+
  |▭▭▭▭■■■■| PlaceholderF07
  +--------+
  bit-mask
  

• The next seven bytes, store each of the seven first bytes of a dstring. If the dstring is less than seven bytes, then the remaining bytes will be instantiated to a default value of zero

• Finally, the last bytes, contain a x64-pointer (8-bytes) to a byte [] (on the heap) for the rest of the bytes in the dstring. If the dstring is less than eight bytes, the byte [] will not be instantiated (null value)

0. Example of a 4-byte dstring ("test"). No heap allocation:

+--------+----+----+----+----+----+----+----+----------+
|□□□□□■□□|0x74|0x65|0x73|0x74|0x00|0x00|0x00|  <NULL>  |
+--------+----+----+----+----+----+----+----+----------+
 bit-mask  b0   b1   b2   b3   b4   b5   b6    pointer
           ——   ——   ——   ——

1. Example of a +8-byte dstring ("Danish string") + heap allocation:

                                         0x551A4290 (byte[] on heap)
                                              |
                                              v
+--------+----+----+---+----+----------+      +----+----+---+----+
|□□□□■□□□|0x44|0x61| … |0x20|0x551A4290| ---> |0x73|0x74| … |0x67|
+--------+----+----+---+----+----------+      +----+----+---+----+
 bit-mask  b0   b1   …   b6    pointer          b7   b8   …   bn
           ——   ——       ——    ———————          ——   ——       ——

2. Example of an array of nine dstring:

extra allocated byte arrays on heap ----+------------+------------+
                                        |            |            |
                                        v            |            |
                                   0x6796EE96        |            |
+-+----+-----------------------+        |            |            |
|i|memo|   continuous memory   |        v            |            |
+-+----+--------+---+----------+        +---+        v            |
|0|0x00|□□□□■□□□| … |0x6796EE96| -----> | … |   0x53EB31F6        |
+-+----+--------+---+----------+        +---+        |            |
|1|0x10|□□□□□□■□| … |  <NULL>  |                     v            |
+-+----+--------+---+----------+                     +---+        v
|2|0x20|□□□□■□□□| … |0x53EB31F6| ------------------> | … |   0x4A424B5E
+-+----+--------+---+----------+                     +---+        |
|…|0x…0|□□□□□■□■| … |  <NULL>  |                                  v
+-+----+--------+---+----------+                                  +---+
|8|0x80|□□□□■□□□| … |0x4A424B5E| -------------------------------> | … |
+-+----+--------+---+----------+                                  +---+

Project structure

├── SpiseMisu.Text.Dstring
│   ├── lib
│   │   └── utils.fs
│   ├── SpiseMisu.Text.Dstring.fsproj
│   └── dstring.fs
├── SpiseMisu.Text.Dstring.Perfs
│   ├── SpiseMisu.Text.Dstring.Perfs.fsproj
│   └── program.fs
├── SpiseMisu.Text.Dstring.Tests
│   ├── SpiseMisu.Text.Dstring.Tests.fsproj
│   ├── program.fs
│   └── tests.fs
├── demo
│   └── dstring.fsx
├── imgs
│   ├── docs
│   ├── licenses
│   └── nuget
├── SpiseMisu.Text.Dstring.sln
├── global.json
├── license.txt
├── license_cil-bytecode_agpl-3.0-only.txt
├── license_knowhow_cc-by-nc-nd-40.txt
├── readme.md
└── todo.org

Memory layout

Heap dump with dotnet-dump mini-guide

0. In ./SpiseMisu.Text.Dstring.Perfs/program.fs > x.GlobalCleanup () = outcomment System.Threading.Thread.Sleep(15_000 (* 15 secs *))

1. Execute ./dotnet-cli-pidof.sh and you will see all the dotnet apps running. Look for the ones ending with SpiseMisu.Text.Dstring.Perfs-Job-OVERNF-1/bin/Release/net10.0.

2. Now wait for the job, you want to make the memory dump for, reaches the clean-up section: // AfterActualRun

3. Execute dotnet-dump collect --type Heap --process-id 2456129 and you will see:

// AfterActualRun
WorkloadResult   1: 2 op, 507459083.00 ns, 253.7295 ms/op
// GC:  8 7 0 207217488 2
// Threading:  0 0 2
 
[createdump] Gathering state for process 2456129 dotnet
[createdump] Writing minidump with heap to file ~/…/SpiseMisu.Text.Dstring/core_20251004_170724
[createdump] Written 596156416 bytes (145546 pages) to core file
[createdump] Target process is alive
[createdump] Dump successfully written in 306ms

4. Investigate by typing: dotnet-dump analyze core_20251004_170724

5. In the tool, type: dumpheap -stat and you will see:

…
561d22bacde0    13,565     539,936 Free
7f54cec830c0         1   8,000,024 System.Int64[]
7f54cec82ee8         1  16,000,024 SpiseMisu.Text+Dstring[]
7f54cec82010         2  16,000,048 System.Byte[][]
7f54ce9aeb48        34  24,004,640 System.String[]
7f54ce90d7c8 3,000,708 158,772,680 System.String
7f54ceb75950 5,000,005 209,002,292 System.Byte[]
Total 8,015,865 objects, 432,486,422 bytes

6. See details for a given memory address: dumpheap -mt 7f54cec82ee8

         Address               MT           Size
    7f14ce800048     7f54cec82ee8     16,000,024

7. You can now drill further by typing: dumparray -length 5 7f14ce800048

Name:        SpiseMisu.Text+Dstring[]
MethodTable: 00007f54cec82ee8
EEClass:     00007f54cec82e60
Size:        16000024(0xf42418) bytes
Array:       Rank 1, Number of elements 1000000, Type VALUETYPE
Element Methodtable: 00007f54cec82db0
[0] 00007f14ce800058
[1] 00007f14ce800068
[2] 00007f14ce800078
[3] 00007f14ce800088
[4] 00007f14ce800098

8. And now we can see the contents of some of the (struct) elements in our array by typing: db -c 80 00007f14ce800058 (16-byte element x 5 = 80-bytes):

00007f14ce800058: 30 6b 22 ce 14 7f 00 00 08 73 9a ac 37 c9 be ba  0k"......s..7...
00007f14ce800068: 58 6b 22 ce 14 7f 00 00 08 53 d1 20 a4 46 a1 86  Xk"......S. .F..
00007f14ce800078: 80 6b 22 ce 14 7f 00 00 08 44 8f d6 ea 76 37 34  .k"......D...v74
00007f14ce800088: a8 6b 22 ce 14 7f 00 00 08 5b c1 41 f8 f9 bd 58  .k"......[.A...X
00007f14ce800098: d0 6b 22 ce 14 7f 00 00 08 50 72 ef 42 a5 6a 2a  .k"......Pr.B.j*

which show a similar pattern as the hex dumper (Dstring.Memory.dump):

0112748739DB99|00001000|↔|00007F536E755118|459055102CAE09F54B
01E606DBB4F6FA|00001000|↔|00007F536E754DD8|4BBC8ED0A25F0B8755
07BDEDF50B83AC|00001000|↔|00007F536E754DB0|43A0DFEEA191AEA2A3
0C5FB78013D42F|00001000|↔|00007F536E754CC0|41854A8815FE6E6A3C
1F3A8D9CC33F5E|00001000|↔|00007F536E7550F0|4BA36307910E82AB70

NOTE: In the performance benchmark Guid's are byte[]-reversed.

> 0112748739DB99|08|↔|00007F536E755118
  (byte reversed becomes)
> 18 51 75 6E 53 7F 00 00|08|99 DB 39 87 74 12 01
  (and compared to `dotnet-dump`)
< 30 6b 22 ce 14 7f 00 00 08 73 9a ac 37 c9 be ba

9. Once you are done, clean the core_[DATESTAMP]_[TIMESTAMP] files

Benchmarks

// * Summary *

BenchmarkDotNet v0.15.6, Linux NixOS 25.05 (Warbler)
12th Gen Intel Core i7-12800H 0.40GHz, 1 CPU, 20 logical and 14 physical cores
.NET SDK 10.0.100
  [Host]     : .NET 10.0.0 (10.0.0, 10.0.25.52411), X64 RyuJIT x86-64-v3 DEBUG
  Job-NTWEWU : .NET 10.0.0 (10.0.0, 10.0.25.52411), X64 RyuJIT x86-64-v3

Job=Job-NTWEWU  Runtime=.NET 10.0  IterationCount=1  
LaunchCount=0  WarmupCount=0  Error=NA  

| Method                                            | N       | Mean         | Ratio  | Allocated | Alloc Ratio |
|-------------------------------------------------- |-------- |-------------:|-------:|----------:|------------:|
| 'Array.zeroCreate<string> x.N'                    | 1000000 |     494.9 us |   1.00 |   7.63 MB |        1.00 |
| 'Array.zeroCreate<dstring> x.N'                   | 1000000 |     672.2 us |   1.36 |  15.26 MB |        2.00 |
| 'x.guids |> Array.map Encoding.ASCII.GetString'   | 1000000 |  54,606.6 us | 110.33 |  61.04 MB |        8.00 |
| 'x.guids |> Array.map Dstring.Bytes.toDstring'    | 1000000 |  51,448.0 us | 103.95 |  53.41 MB |        7.00 |
| 'x.sha256s |> Array.map Encoding.ASCII.GetString' | 1000000 |  72,909.0 us | 147.31 |  91.55 MB |       12.00 |
| 'x.sha256s |> Array.map Dstring.Bytes.toDstring'  | 1000000 |  60,189.2 us | 121.61 |  68.66 MB |        9.00 |
| 'x.int64s |> Array.map Encoding.ASCII.GetString'  | 1000000 |  75,732.9 us | 153.02 |  45.78 MB |        6.00 |
| 'x.int64s |> Array.map Dstring.Bytes.toDstring'   | 1000000 |   8,107.6 us |  16.38 |  15.26 MB |        2.00 |
| 'x.strings |> Array.sort'                         | 1000000 | 209,608.7 us | 423.51 |   7.63 MB |        1.00 |
| 'x.strings |> Array.sortDescending'               | 1000000 | 238,639.4 us | 482.16 |   7.63 MB |        1.00 |
| 'x.strings |> Array.map Dstring.UTF8.fromString'  | 1000000 | 130,051.8 us | 262.77 |  53.39 MB |        7.00 |
| 'x.dstrings |> Array.map Dstring.UTF8.toString'   | 1000000 | 135,886.5 us | 274.55 |  98.69 MB |       12.94 |
| 'x.dstrings |> Dstrings.sort'                     | 1000000 | 168,288.2 us | 340.02 |  15.26 MB |        2.00 |
| 'x.dstrings |> Dstrings.sortDescending'           | 1000000 | 168,100.8 us | 339.64 |  15.26 MB |        2.00 |
| 'x.dstrings |> Dstrings.sortPrefix'               | 1000000 | 147,110.7 us | 297.23 |  15.26 MB |        2.00 |
| 'x.dstrings |> Dstrings.sortPrefixDescending'     | 1000000 | 149,646.4 us | 302.36 |  15.26 MB |        2.00 |

// * Hints *
HideColumnsAnalyser
  Summary -> Hidden columns: Error

// * Legends *
  N           : Value of the 'N' parameter
  Mean        : Arithmetic mean of all measurements
  Ratio       : Mean of the ratio distribution ([Current]/[Baseline])
  Allocated   : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  Alloc Ratio : Allocated memory ratio distribution ([Current]/[Baseline])
  1 us        : 1 Microsecond (0.000001 sec)

NOTE: By adding pinnedLastByte for dstrings that are exactly 8-byte in size, we minimize the amount of instantiated byte[]. Compare to previous approach (see below, before and after):

| Method                                            | N       | Mean       | Ratio  | Allocated | Alloc Ratio |
|-------------------------------------------------- |-------- |-----------:|-------:|----------:|------------:|
| 'Array.zeroCreate<string> x.N'                    | 1000000 |   2.419 ms |   1.00 |   7.63 MB |        1.00 |
| …                                                 |      …  |          … |      … |         … |           … |
| 'x.int64s |> Array.map Encoding.ASCII.GetString'  | 1000000 |  84.291 ms |  34.85 |  45.78 MB |        6.00 |
| 'x.int64s |> Array.map Dstring.Bytes.toDstring'   | 1000000 |  51.341 ms |  21.23 |  45.78 MB |        6.00 |
| …                                                 |      …  |          … |      … |         … |           … |
| …                                                 |      …  |          … |      … |         … |           … |
| 'x.int64s |> Array.map Encoding.ASCII.GetString'  | 1000000 |  83.702 ms |  28.04 |  45.78 MB |        6.00 |
| 'x.int64s |> Array.map Dstring.Bytes.toDstring'   | 1000000 |  11.347 ms |   3.80 |  15.26 MB |        2.00 |
| …                                                 |      …  |          … |      … |         … |           … |

That would be a reduction x5.5 on compuation time and x3 on (heap) memory allocation.

This will be really useful/helpful for when storing basic types, as for example: DateTime; float64; int64/uint64; …, as dstrings.

Licenses

Source code in this repository is ONLY covered by a Server Side Public License, v 1 while the rest (knowhow, text, media, …), is covered by the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International license.

However, as it's not permitted to deploy a nuget package with non OSI nor FSF licenses:

Pushing SpiseMisu.Text.Dstring.0.11.0.nupkg to 'https://www.nuget.org/api/v2/package'...
  PUT https://www.nuget.org/api/v2/package/
  BadRequest https://www.nuget.org/api/v2/package/ 846ms
error: Response status code does not indicate success: 400 (License expression must only contain licenses that are approved by Open Source Initiative or Free Software Foundation. Unsupported licenses: SSPL-1.0.).

The CIL-bytecode content of the nuget package is therefore dual-licensed under the GNU Affero General Public License v3.0 only and the rest (knowhow, text, media, …), is covered by the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International license.

For more info on compatible nuget packages licenses, see SPDX License List.