Single byte string in C# nl

Door creator1988 op donderdag 16 december 2010 14:26 - Reacties (14)
Categorie: Algoritmes, Views: 3.954

Definitie van een string
In .NET is een string een verzameling karakters in Unicode. Hierdoor zijn er twee bytes per karakter nodig, plus twee bytes voor het aantal karakters in de string.

C#:
1
2
3
4
// de string "A" staat in memory als de volgende 4 bytes:
00 01 00 41
// twee bytes met het getal 1, voor het aantal elementen (1 dus)
// twee bytes met de code voor de letter, in dit geval 0x41


Voordeel hiervan is dat bijna alle karakters in een string kunnen voorkomen. Nadeel is dat wanneer je alleen 'eenvoudige' karakters gebruikt (geen fancy tekens als Š of U+263A) dat je twee keer zoveel geheugen alloceert dan eigenlijk nodig is. Normaal geen enkel probleem.

Maar als geheugengebruik kritisch is?
Wanneer je geheugengebruik een belangrijk punt van je applicatie is, en er bovendien veel (en ik bedoel hier vťťl) strings hebt, dan kan het geheugengebruik een probleem worden. Oplossing is om je strings op te slaan als arrays van 'bytes' in plaats van 'char'. Een byte heeft namelijk een width van 1 byte (what's in a name). Je kunt dan alleen wel maximaal 255 verschillende karakters gebruiken in je strings.


Implementatie
Hieronder een simpele implementatie van bovenstaand principe met een voorbeeldimplementatie van 'StartsWith' en 'Equals':

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static class StringExtender
{
    public static byte[] ToOneWidthByteArray(this string s)
    {
        if (s.Any(c => c > 255))
            throw new ArgumentException("Chars with an ASCII value of over 255 are not supported");

        return s.Select(ch => (byte)ch).ToArray();
    }
}

public static class ByteArrayExtender
{
    public static bool StartsWith(this byte[] b, string value)
    {
        for (int i = 0; i < value.Length; i++)
        {
            if ((byte) value[i] != b[i]) return false;
        }
        return true;
    }

    public static bool Equals(this byte[] b, string value)
    {
        if (value.Length != b.Length) return false;

        return b.StartsWith(value);
    }
}



Performance
Om ook iets zinnigs te kunnen zeggen over de performance hebben we een testje nodig! Even 1.000.000 miljoen strings vergelijken (bovenstaande implementatie van 'StartsWith' tegen de native 'String.StartsWith').

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string comparisonString = "amsterdam";
for (int i = 0; i < 1000000; i++)
{
    // doe een Ordinal startsWith (snelste)
    bool x = comparisonString.StartsWith("a", StringComparison.Ordinal);
}
// String.StartsWith took 42,15 ms.

// Let op! Deze methode wordt ook meegenomen in de timing.
byte[] comparisonByteArray = "amsterdam".ToOneWidthByteArray();
for (int i = 0; i < 1000000; i++)
{
    bool y = comparisonByteArray.StartsWith("a");
}
// Byte[].StartsWidth took 51,75 ms.



Dus?
Performance is wat minder, maar het geheugengebruik scheelt aanzienlijk (in onze case van 300 MB -> 190 MB). De performance-loss is weliswaar +20% maar in de praktijk niet merkbaar. Mocht je dus ooit tegen dit probleem aanlopen; het kŠn een oplossing zijn maar wel met een prijs.

Volgende: Generic retry 12-'10 Generic retry
Volgende: Expression Trees - Espresso voor je code! 12-'10 Expression Trees - Espresso voor je code!

Reacties


Door Tweakers user [ti], donderdag 16 december 2010 14:42

Wat ik eigenlijk interessanter vind om te weten: waar had je 't nou voor nodig?

Door Tweakers user StM, donderdag 16 december 2010 14:46

Zou je hem niet veel sneller moeten kunnen maken dmv unsafe code en het niet gebruiken van LINQ? Volgens mij komt een deel van je performance loss door je implementatie.

Door Tweakers user creator1988, donderdag 16 december 2010 14:47

[ti] schreef op donderdag 16 december 2010 @ 14:42:
Wat ik eigenlijk interessanter vind om te weten: waar had je 't nou voor nodig?
Bezig met een nieuw zoeksysteem voor funda, waar je op alle geografische entiteiten kunt zoeken (dus bv. 'de pijp in amsterdam'); en we hebben alles in verschillende formaten in memory staan om elke zoekopdracht in 5 ms. te vertalen naar een set met suggesties. 600 MB (waarvan 300 aan alleen maar strings) per server om zoiets te serveren is nogal veel.
StM schreef op donderdag 16 december 2010 @ 14:46:
Zou je hem niet veel sneller moeten kunnen maken dmv unsafe code en het niet gebruiken van LINQ? Volgens mij komt een deel van je performance loss door je implementatie.
Mweh, normaal gesproken wel maar LINQ wordt hier alleen gebruikt om de string om te zetten naar bytes, en die operatie is echt fracties van een milliseconde. Unsafe arrays vergelijken gaat waarschijnlijk wel sneller, maar de performance is niet zo slecht dat het nodig is om om dat level te gaan optimaliseren.

[Reactie gewijzigd op donderdag 16 december 2010 14:49]


Door Tweakers user Ventieldopje, donderdag 16 december 2010 14:58

Ik vind 20% nogal wat, juist vooral als je veel strings gebruikt dan heb ik persoonlijk liever dat hij iets meer geheugen gebruik (wordt blijkbaar toch nuttig gebruikt) en sneller is ;)

Maar wel leuk gevonden ;)

Door Tweakers user creator1988, donderdag 16 december 2010 15:05

Phas0r schreef op donderdag 16 december 2010 @ 14:58:
Ik vind 20% nogal wat, juist vooral als je veel strings gebruikt dan heb ik persoonlijk liever dat hij iets meer geheugen gebruik (wordt blijkbaar toch nuttig gebruikt) en sneller is ;)

Maar wel leuk gevonden ;)
Nou, volgens mij is de truc bij zulke grote sets om zo min mogelijk string comparisons te doen. We gebruiken in principe in-memory lookup tables met daarin per 2 karakters een linked list met alle entiteiten:

code:
1
lookup["am"] -> contains Amsterdam, Amstelveen etc.


Daardoor kan je 99,5% van al je potentiŽle matches al weggooien. Daarna doen we een startsWith, en die hit is voor ons vrij goedkoop (de calls worden niet ineens allemaal 20% trager dus).

C#:
1
lookup["am"].Where(a=>a.Key.StartsWith("amster")); // zoiets

[Reactie gewijzigd op donderdag 16 december 2010 15:05]


Door Tweakers user BeerenburgCola, donderdag 16 december 2010 15:13

Heb je ook al aan utf-8 gedacht ?

Kun je wel alle tekens in opslaan en scheelt gemiddeld toch bijna 50% aan ruimte.
(ASCII karakters < 128 nemen by design nog steeds ťťn byte in beslag in utf-8)

Je string compares kan je dan ook nog steeds op byte niveau doen.
Er zijn vast wel bibliotheken voor in C#.

Door Tweakers user creator1988, donderdag 16 december 2010 15:23

BeerenburgCola schreef op donderdag 16 december 2010 @ 15:13:
Heb je ook al aan utf-8 gedacht ?

Kun je wel alle tekens in opslaan en scheelt gemiddeld toch bijna 50% aan ruimte.
(ASCII karakters < 128 nemen by design nog steeds ťťn byte in beslag in utf-8)

Je string compares kan je dan ook nog steeds op byte niveau doen.
Er zijn vast wel bibliotheken voor in C#.
Dat is dan alleen bruikbaar voor het omzetten van String -> Byte Array. Voor zover ik kan vinden zijn er geen string implementaties op basis van UTF8 voor .NET. Maar nee, niet aan gedacht; wel een nuttige toevoeging.

Door Tweakers user PoweRoy, donderdag 16 december 2010 15:31

Een byte heeft namelijk een width van 1 byte (what's in a name). Je kunt dan alleen wel maximaal 255 verschillende karakters gebruiken in je strings.
Dit gaat erg leuk worden als je dus wel exotische characters gaat gebruiken. Theoretisch kan je 255 verschillende characters alleen zijn de eerste 128 ASCII (de basis) goed te gebruiken alleen de laatste 128 (extended ASCII) beschreven in Code Pages. Dus leuk als je dit consequent dit alleen in Nederland doet (bv Code Page Windows-1252) maar in het buitenland wordt dit een feest. (een character heeft dan meerdere betekenissen)

Bij unicode is dit niet omdat alle soort characters een unieke waarde hebben.

Kortom dit soort optimalisaties gaan iets te ver. Geheugen is niet echt kritisch zou ik zeggen, je kan er altijd extra geheugen bij zetten :Y)

@creator1988 heeft bevoorbeeld een heel handige performance increase door gewoon goed om te gaan met resources :)

Door Tweakers user creator1988, donderdag 16 december 2010 15:36

PoweRoy schreef op donderdag 16 december 2010 @ 15:31:
Dit gaat erg leuk worden als je dus wel exotische characters gaat gebruiken. Theoretisch kan je 255 verschillende characters alleen zijn de eerste 128 ASCII (de basis) goed te gebruiken alleen de laatste 128 (extended ASCII) beschreven in Code Pages. Dus leuk als je dit consequent dit alleen in Nederland doet (bv Code Page Windows-1252) maar in het buitenland wordt dit een feest. (een character heeft dan meerdere betekenissen)
Klopt als een bus. In [link=http://glamour.tweakblogs.net/blog/5732/diakritische-tekens-en-soundex-in-net.html]dit artikel[/link] heb ik wat code staan om dat soort data eruit te halen. Ik gebruik dit daarom ook alleen voor genormaliseerde velden die alleen ASCII chars < 127 bevatten. Sowieso kan je je eigen extended ascii set definiŽren als je het wel nodig hebt (als we dan toch aan micro-optimaliseren zijn). Terug naar de DOS tijd zeg maar :) .
Kortom dit soort optimalisaties gaan iets te ver. Geheugen is niet echt kritisch zou ik zeggen, je kan er altijd extra geheugen bij zetten :Y)
Niet waar. Wij hebben nog een aantal webservers die gewoon 32-bits zijn, daar is geheugen wel degelijk een issue. In dit soort gevallen kan het kostenefficiŽnter zijn om je geheugengebruik gewoon goed in de gaten te houden.

Door Tweakers user FlowinG, donderdag 16 december 2010 16:06

Linq is over het algemeen duur, het bespaart misschien geheugen maar kost meer processorkracht. Ik weet niet hoe dit precies verhoud met het Select statement. Maar waarom niet het volgende:


C#:
1
byte[] bytes = System.Text.Encoding.UTF8.GetBytes("bladiebla");



UTF8 is standaard 1 byte tenzij je vreemde karakters hebt.

[Reactie gewijzigd op donderdag 16 december 2010 16:10]


Door Tweakers user creator1988, donderdag 16 december 2010 17:00

FlowinG schreef op donderdag 16 december 2010 @ 16:06:
Linq is over het algemeen duur, het bespaart misschien geheugen maar kost meer processorkracht. Ik weet niet hoe dit precies verhoud met het Select statement. Maar waarom niet het volgende:
Klopt niet helemaal; als je weet hoe LINQ vertaalt is het net zo snel als het uitschrijven.

Anyhow: ja UTF8.GetBytes is significant sneller dan mijn implementatie; had mezelf dat even niet gerealiseerd. Desondanks heeft het niet zo heel veel effect. Het vertalen van string -> bytearray kost relatief gezien namelijk niet zoveel. De vergelijkingen zijn veel duurder.

Door Tweakers user H!GHGuY, donderdag 16 december 2010 18:55

Er zijn ook nog wel efficientere string compares te vinden...
Afhankelijk van de datasets en de operaties kan een radix tree/patricia tree ook aangeraden zijn.

Door Boon, donderdag 16 december 2010 21:54

Zeg, creator1988. Aan je manier van schrijven denk ik dat je religieus bent.

Klopt dat?

Vr Gr,

Door Tweakers user creator1988, vrijdag 17 december 2010 01:38

H!GHGuY schreef op donderdag 16 december 2010 @ 18:55:
Er zijn ook nog wel efficientere string compares te vinden...
Afhankelijk van de datasets en de operaties kan een radix tree/patricia tree ook aangeraden zijn.
Ja, efficiŽnter geloof ik wel, maar volgens mij is elke tree based methode sowieso minder efficiŽnt qua geheugengebruik, waar het hier dan weer more or less om ging. Sowieso doen we al ongeveer hetzelfde als in dit soort methodes door een lookuptable op de eerste twee chars te maken.
Boon schreef op donderdag 16 december 2010 @ 21:54:
Zeg, creator1988. Aan je manier van schrijven denk ik dat je religieus bent.

Klopt dat?
Uh lol whut? En nee.

Reageren is niet meer mogelijk