[C] Correcte implementatie van periodieke functies

[CurlyMo]

In mijn C applicatie maak ik gebruik van een threadpool om met een beperkt aantal threads mijn functies af te handelen. Nu werken veel van die functies op basis van events. Echter zijn er ook functies die periodiek dienen plaats te vinden. De vraag is hoe je dit nu het beste implementeert. Er kunnen tientallen periodieke functies tegelijk aan het wachten zijn op uitvoering. Voorbeelden zijn:
- Elke drie seconden een cpu/ram gebruik opvraging.
- Elke zonsopgang / zonsondergang een event.
- Elke 24 uur een ntp-sync
- Elk uur een API aanvraag.
- Communiceren van de tijd via een klok functie.

Deze functies moeten ook afgehandeld worden door de threadpool. Nu heb ik dit op twee manieren proberen op te lossen van welke ik beide ontevreden was. In beide manieren stond dit stukje pseudocode centraal:

code:

func teller() {
    tik elke (milli)seconde (of wordt elke (milli)second aangeroepen)
    loop door periode threads
        als voldoende seconde gepasseerd, voer thread aan threadpool
}

De time-based threads registreren zich in dit voorbeeld in een pool welke elke (milli)seconde doorgelopen wordt om te zien om er al voldoende tijd is verstreken om de functie uit te voeren. Nu heb ik deze functie dus op twee manieren proberen te integreren:

1. Voer de teller elke (milli)seconde uit vanuit een timer. Probleem is dat dit niet veilig is qua deadlocks. De timer wacht namelijk niet totdat de functie klaar is voordat hij opnieuw wordt aangeroepen.
2. Start een aparte thread met een loop welke elke seconde alle functies nagaat. Probleem hier is dat de evaluatie tijd teveel lacency teweeg brengt waardoor ik uiteindelijk (milli)seconden mis in mijn klok.

Ik zoek dus naar een manier om deze functionaliteit goed in te bedden in mijn bestaande threadpool structuur, maar wel met een hoge betrouwbaarheid, accuraatheid en snelheid. Idealiter behaal ik een resolutie van 1 milliseconde.

[Sissors]

Lijkt mij dat je wil dat alleen je timer functie wordt aangeroepen als hij daadwerkelijk iets moet doen, niet om te kijken of hij mogelijk iets zou moeten doen.

Gebaseerd op: https://github.com/mbedmi.../mbed/common/ticker_api.c

Je wilt een lijst met volgende tijden hebben dat iets moet gebeuren (kan zowel enkel lijst met tijden zijn, of gewoon loopen door de threads en aan elke vragen wanneer de volgende keer is dat hij wil plaatsvinden). Pak die tijd, trek huidige tijd ervanaf, en over zoveel (milli) seconde moet die functie worden uitgevoerd, dus je kan een timer achtig iets aanzetten die over zoveel tijd je een zeintje geeft. Afhankelijk van hoe je het precies implementeert moet je iig elke keer als je een nieuw iets eraan toevoegt opnieuw gekeken worden wanneer de eerstvolgende functie moet worden uitgevoerd. En mogelijk ook als je laatste functie is uitgevoerd kijken wanneer de volgende is. (In dat voorbeeld dat ik linkte gebruiken ze een gesorteerde linked list, waardoor je voor de volgende uit te voeren functie altijd de eerste uit je linked list kan gebruiken).

[Soultaker]

Ik ben het met sissors eens: je moet je callbacks in een datastructuur opslaan die bijhoudt wanneer de eerstvolgende uitgevoerd moet worden. Dat kan met een sorted set of een priority queue of iets dergelijks.

Bedenk wel dat het mogelijk is dat een nieuwe callback toegevoegd wordt met een timeout vóór het eerste element in de queue. In dat geval moet je de scheduler kunnen onderbreken, zodat die niet blijft slapen.

Hoe het slapen/onderbreken precies werkt is systeem-afhankelijk.

[farlane]

Begrijp ik het goed: je scheduler functie duurt langer dan de tick van je scheduler?

[CurlyMo]

farlane schreef op woensdag 09 december 2015 @ 11:37:
Begrijp ik het goed: je scheduler functie duurt langer dan de tick van je scheduler?

In de huidige implementatie wel, vandaar dat ik ook tot de conclusie kwam dat het zo niet werkt

[jeroen3]

Laat elke taak een systeemtijd retourneren via een api wanneer de taak weer gewekt wil worden.
Systeemtijd kan een eigen tijdseenheid zijn (ms sinds start), of de unix timestamp (met milliseconden, in 64 bit).

In je scheduler hoef je alleen via een linked list de eerste te zoeken, met de hoogste prioriteit. De thread een signal te geven (reden van uitvoeren: trhead api, signal stop, user event).
Duurt dit zoeken langer dan 1ms, dan is je cpu is te traag, of je specificaties te strak.
Of je hebt teveel taken, in dan geval moet je misschien een tickless scheduler maken.

Menig (embedded real-time) operating system werkt zo. Kijk het anders af van ChibiOS.

[CurlyMo]

Sissors schreef op woensdag 09 december 2015 @ 09:32:
Lijkt mij dat je wil dat alleen je timer functie wordt aangeroepen als hij daadwerkelijk iets moet doen, niet om te kijken of hij mogelijk iets zou moeten doen.

Zo simpel kan het zijn

[MSalters]

jeroen3 schreef op woensdag 09 december 2015 @ 11:45:
In je scheduler hoef je alleen via een linked list de eerste te zoeken, met de hoogste prioriteit. De thread een signal te geven (reden van uitvoeren: trhead api, signal stop, user event).
Duurt dit zoeken langer dan 1ms, dan is je cpu is te traag, of je specificaties te strak ...

of je datastructuur verkeerd. Dit is een standaard situatie waarin je een priority queue gebruikt, geen linked list.

[CurlyMo]

MSalters schreef op donderdag 10 december 2015 @ 23:56:
[...]

of je datastructuur verkeerd. Dit is een standaard situatie waarin je een priority queue gebruikt, geen linked list.

Of een sorted linked list? Waarin dus de eerste elementen altijd het eerste uitgevoerd dienen te worden.

[CurlyMo]

Een eerste opzet gemaakt, maar een milliseconde resolutie halen is toch lastiger dan gedacht.

(Getallen in nanoseconde zoals de invoer van itimerspec)

C:

timer_add_task(timer, "a", 2000, printtime);
timer_add_task(timer, "b", 1000, printtime);
timer_add_task(timer, "c", 3000, printtime);
timer_add_task(timer, "d", 1000, printtime);
timer_add_task(timer, "e", 3000, printtime);
timer_add_task(timer, "f", 4000, printtime);
timer_add_task(timer, "g", 5000, printtime);
timer_add_task(timer, "h", 6000, printtime);
timer_add_task(timer, "i", 7000, printtime);
timer_add_task(timer, "j", 8000, printtime);
timer_add_task(timer, "k", 9000, printtime);    

De printtime functie bestaat uit niks meer dan het printen van de tijd.

De uitvoer van dit alles:

code:

d 2015:12:11 16:41:19.525209
b 2015:12:11 16:41:19.525214
a 2015:12:11 16:41:19.527219
e 2015:12:11 16:41:19.529204
c 2015:12:11 16:41:19.529208
f 2015:12:11 16:41:19.531217
g 2015:12:11 16:41:19.533224
h 2015:12:11 16:41:19.535215
i 2015:12:11 16:41:19.537216
j 2015:12:11 16:41:19.539207
k 2015:12:11 16:41:19.541221

Probleem is dus dat de resolutie blijft steken op +/- 2 milliseconde. Zelfs als ik het geheel op nanosecondes wil laten uitvoeren, dan blijft de overhead toch 2 milliseconde.

De aanpak die ik nu heb gekozen.
1. Initieer een timer.
2. Voeg een taak toe aan de timer pool in een sorted linked list.

3. Alle taken van 1 milliseconde worden uitgevoerd.
4. Van alle overige taken wordt nu 1 milliseconde afgetrokken (het is immers een sorted linked list).
5. De timer wordt gezet op de delay van de eerste taak en stap 3, 4, en 5 worden herhaald totdat de taken op zijn of er nieuwe taken worden toegevoegd.

---

De overhead lijkt te zitten in timer_settime. Als ik gewoon een loop maak tussen timer_settime -> callback -> timer_settime -> callback -> enz. dan haal ik nog geen hogere resolutie dan 2 milliseconde.

[ Voor 5% gewijzigd door CurlyMo op 11-12-2015 17:31 ]

[.oisyn]

CurlyMo schreef op vrijdag 11 december 2015 @ 17:07:
Probleem is dus dat de resolutie blijft steken op +/- 2 milliseconde. Zelfs als ik het geheel op nanosecondes wil laten uitvoeren, dan blijft de overhead toch 2 milliseconde.

Hou er rekening mee dat printen naar console best veel overhead met zich mee kan brengen.

De aanpak die ik nu heb gekozen.
1. Initieer een timer.
2. Voeg een taak toe aan de timer pool in een sorted linked list.

3. Alle taken van 1 milliseconde worden uitgevoerd.
4. Van alle overige taken wordt nu 1 milliseconde afgetrokken (het is immers een sorted linked list).
5. De timer wordt gezet op de delay van de eerste taak en stap 3, 4, en 5 worden herhaald totdat de taken op zijn of er nieuwe taken worden toegevoegd.

Dat zou ik anders implementeren. Waarom overal tijd vanaf trekken, als je in plaats daarvan ook net zo goed kunt opslaan wanneer ze moeten optreden (ipv hoe lang het nog duurt, wat ook nog eens cumulatieve rekenfouten met zich mee gaat brengen)? Op het moment dat je iets wilt schedulen voor "over 3 milliseconden", dan pak je gewoon huidige tijd + 3 ms.

De overhead lijkt te zitten in timer_settime. Als ik gewoon een loop maak tussen timer_settime -> callback -> timer_settime -> callback -> enz. dan haal ik nog geen hogere resolutie dan 2 milliseconde.

Hoeft niet per se overhead te zijn, maar kan ook gewoon te maken hebben met de granulariteit van de timer. Als je echt milliseconde-precisie timings wilt hebben dan zul je sowieso al snel moeten overstappen op een realtime OS.

[farlane]

Welk platform hebben we het hier over eigenlijk? Je post impliceert Posix (Linux?), maar om een ms resolutie te halen zal je wel een RT versie moeten hebben .....

[edit]
Wat .oisyn zegt dus...

[ Voor 12% gewijzigd door farlane op 11-12-2015 17:49 ]

[CurlyMo]

Inderdaad een Posix Linux / FreeBSD. Ik dacht dat ms nog wel haalbaar zou moeten zijn.

Ik ga het een en ander eens anders proberen te doen en kijken welke resolutie dan haalbaar is.

---

Aanvullend op mijn timer_settime overhead opmerking. Als ik de timer interval op 1 milliseconde zet dan is hij heerlijk precies. De timer zelf kan het dus wel. De overhead zit er dan toch op een of andere manier in het updaten van de timer_settime.

code:

2015:12:11 18:35:48.290631
2015:12:11 18:35:48.291683
2015:12:11 18:35:48.292674
2015:12:11 18:35:48.293666
2015:12:11 18:35:48.294655
2015:12:11 18:35:48.296747
2015:12:11 18:35:48.297654
2015:12:11 18:35:48.298633
2015:12:11 18:35:48.299657
2015:12:11 18:35:48.300656
2015:12:11 18:35:48.301653
2015:12:11 18:35:48.302633
2015:12:11 18:35:48.303650
2015:12:11 18:35:48.304687
2015:12:11 18:35:48.305632
2015:12:11 18:35:48.306687

[ Voor 66% gewijzigd door CurlyMo op 11-12-2015 18:37 ]

[MSalters]

CurlyMo schreef op vrijdag 11 december 2015 @ 09:44:
[...]
Of een sorted linked list? Waarin dus de eerste elementen altijd het eerste uitgevoerd dienen te worden.

Nogal duur om die sorted te houden. Insertion is O(N).

[CurlyMo]

Ander probleem wat ik al voorzag (via de threadpool uiteindelijk en met een iets ander doen dan louter printer ):

code:

2015:12:11 20:16:03.962865
2015:12:11 20:16:04.989180
2015:12:11 20:16:06.981
2015:12:11 20:16:07.19182
2015:12:11 20:16:08.21476

Een van de eisen is het printen van een klok. Echter mag deze klok geen secondes missen zoals je hier ziet. Dat gebeurt dus wel in de timer_settime > callback > timer_settime methode. Is dan de enige optie een dedicated timer gebruiken met een interval van 1 seconde?

Nu ook bezig met het omzetten naar de TIMER_ABSTIME. Lijkt inderdaad makkelijker.

[ Voor 7% gewijzigd door CurlyMo op 11-12-2015 20:47 ]

[farlane]

Wat je ook probeert, het systeem zal er niet realtime door worden : vroeg of laat besluit je OS dat er iets anders belangrijker is.
Als je het doet doe het dan goed en neem een realtime systeem. Je zou (als je Linux gebruikt) eens kunnen kijken of de preempt-rt patch wat voor je kan betekenen.

[ Voor 3% gewijzigd door farlane op 11-12-2015 20:53 ]

[CurlyMo]

Ik kan me gewoon moeilijk voorstellen dat iets als het printen van een klok niet op ieder regulier OS stabiel zou moeten kunnen. Millisecondes als te hoge resolutie geloof ik wel. Ik kan er ook mee leven dat ik geen 100% garantie heb bij een klok, maar 99% zou toch moeten lukken met wanneer nodig een dedicated timer met een interval?

Het doel is uiteindelijk dat gebruikers deze regels kunnen maken (wat nu op zich goed werkt, maar dan op een niet houdbare manier met tientallen threads):

code:

IF datetime.seconds == 0 THEN ...

Dit mag desnoods ook best dit zijn:

code:

IF datetime.seconds == 0 OR datetime.second == 1 THEN ...

Moet toch kunnen?

[Matis]

Als je realtime gedrag wilt, zul je een RTOS, bijvoorbeeld QNX (Linux) of ChibiOS moeten nemen.
Wanneer wij binnen onze embedded platformen zekerheid willen dat iets op gezette tijden gebeurt en dat het ook altijd even lang duurt, nemen we een FPGA of DSP.
Binnen een multithreaded OS kun je geen realtime gedrag eisen. Zelf met RT patches, blijf je afhankelijk van de kwaliteiten van de programmeur en de duur van je event handlers.

[CurlyMo]

Ik kom er net achter dat ik helemaal in de verkeerde unit aan het denken ben.

2000 voeren aan itimerspec betekend helemaal geen 2 milliseconde, maar 2 microseconde Ik krijg dus geen microseconde resolutie, maar dat is ook helemaal niet nodig. Ik wil milliseconde resolutie, dus 2000000 nanoseconden. Dat werkt dus wel betrouwbaar genoeg

[farlane]

Dat werkt dus wel betrouwbaar genoeg

Strekking van het verhaal blijft hetzelfde: als het geen realtime OS is, heb je geen enkele garantie.

Matis schreef op vrijdag 11 december 2015 @ 23:51:
Binnen een multithreaded OS kun je geen realtime gedrag eisen.

Tuurlijk kun je dat wel eisen: QNX, ChibiOS en ook bv FreeRTOS zijn multithreaded realtime OSen.

Zelf met RT patches, blijf je afhankelijk van de kwaliteiten van de programmeur en de duur van je event handlers.

Dat blijf je altijd, ook op een realtime OS, ook als je het in hardware doet.

[ Voor 14% gewijzigd door farlane op 12-12-2015 19:04 ]

[Sissors]

MSalters schreef op vrijdag 11 december 2015 @ 19:41:
[...]

Nogal duur om die sorted te houden. Insertion is O(N).

Waarbij in zulk soort situatie N ruwweg 10 ofzo zal zijn, oftewel enorm goedkoop. Het lijkt me ook niet dat je met een priority queue veel opschiet, je wilt gewoon de tijd hebben wanneer je volgende timer event moet plaatsvinden.

[Gomez12]

Sissors schreef op zondag 13 december 2015 @ 09:31:
[...]

Waarbij in zulk soort situatie N ruwweg 10 ofzo zal zijn, oftewel enorm goedkoop.

Let er met dat soort overwegingen wel goed op dat je alles monitored en logged etc.

Het zou niet de eerste keer zijn dat ik een situatie zie ontstaan waar er 11 per seconde binnenkomen en er maar 10 uitgaan en dat net zolang tot er een paar miljard in de queue staan na een paar dagen en dan zie je je systeem langzaam omvallen omdat sorted list sorteren steeds zwaarder wordt en aan het eind van de rit wel eens richting 100% cpu kan gaan.

[CurlyMo]

Hier hebben inderdaad alle linked lists een maximale toegestane lengte welke normaal gesproken nooit gehaald mag worden.

[.oisyn]

Sissors schreef op zondag 13 december 2015 @ 09:31:
Het lijkt me ook niet dat je met een priority queue veel opschiet, je wilt gewoon de tijd hebben wanneer je volgende timer event moet plaatsvinden.

Waarom zou dat niet opschieten met een priority queue? Het eerstvolgende event staat vooraan in de queue

[CurlyMo]

.oisyn schreef op zondag 13 december 2015 @ 21:06:
[...]

Waarom zou dat niet opschieten met een priority queue? Het eerstvolgende event staat vooraan in de queue

Het doel is toch gewoon het voorsorteren van taken? Of dat nu via een gesorteerde linked list is of via een priority queue. Op dit moment heb ik (nog) geen aanwijzingen dat de linked list een bottleneck is.

[.oisyn]

Lees nog eens goed waar ik op reageer

[CurlyMo]

.oisyn schreef op zondag 13 december 2015 @ 21:37:
Lees nog eens goed waar ik op reageer

Dat zag ik Ik bedoel echter of het discussiëren over een sorted linked list vs priority queue niet een discussie in de marge is.

[.oisyn]

Dat hangt natuurlijk van je use case af. Je kunt je echter afvragen of het in eerste instantie een handige keuze is geweest om voor een datastructuur te kiezen die niet automatisch al doet wat je wilt, zodat je die boilerplate er zelf omheen moet bouwen. Een prio queue is natuurlijk niet alleen efficienter (bij grote N) - conceptueel past het gewoon beter bij je requirements.

[CurlyMo]

Vanuit mijn situatie kan ik zeggen dat ik sowieso bezig ben met een grote inhaalslag met de kennis van nu. Dus heb nu een threadpool i.p.v. tientallen threads, een eventpool i.p.v. meerdere polls/selects, een timerpool i.p.v. een loop elke seconde. Dan komt het omzetten van een sorted linked list naar een priority queu later wel. Op dat laatste moet ik me nog even goed inlezen om het te kunnen implementeren

[Sissors]

@Oisyn, Waarom? Wat je conceptueel wil hebben is de tijd waarop het eerstvolgende event gaat gebeuren. Een sorted linked list lijkt me daarvoor conceptueel ideaal. En ik denk dat ik wat mis (met wikipedia ernaast), want ik zie niet echt het voordeel van een priority queue in. Als je die gebruikt om vervolgens in volgorde de events eruit te halen, dan doe je toch uiteindelijk gewoon hetzelfde? Uiteindelijk moet je iets van een sorting algoritme gebruiken om hem gesorteerd te houden.

[Soultaker]

Een priority queue wordt meestal geïmplementeerd als een array met heap-structuur. Daarin kun je in O(log N) tijd elementen toevoegen, en in O(log N) het eerste element eruit halen. Ten eerste is dat efficiënter dan elementen toevoegen aan een linked list (dat kost O(N) tijd) en ten tweede is een array compacter en dus sneller dan een linked list (waarbij je geen spatial locality hebt omdat elk element op een willekeurige plek in het geheugen staat, en de cache dus minder benut wordt).

[Sissors]

Ah natuurlijk: Ik zat zelf te denken dat je ook gewoon binaire search tree om een sorted linked list kan doen bij invoegen, maar dat lukt natuurlijk niet omdat je niet weet waar het midden is, dus je moet gewoon van voor af aan beginnen. Duidelijk.

Dan is een priority queue inderdaad efficienter (effectief dus gewoon een array van tijden wanneer iets moet worden uitgevoerd + een pointer/ID of dat iets als ik het goed begrijp) (wel afhankelijk van of je misschien opzoeken belangrijker vindt om snel te gaan dan erin stoppen). Tegelijk blijft dit voor deze toepassing denk ik toch vooral een theoretisch probleem: Het lijkt me niet dat je snel meer dan een stuk of 10 elementen zal hebben hier.

[MSalters]

Met 10 elementen is een linked list sowieso niet zinnig, gebruik gewoon een array. Matige locality of reference is misschien wel de meest onderschatte oorzaak van slechte performance.

[CurlyMo]

Wat zijn dan de vuistregels voor het gebruik van een array, linked list, heap, enz.? Nu pas ik zelf op alles gewoon een linked list toe. Desnoods als een FIFO.

[Zoijar]

Out of the box linked list gebruik je eigenlijk nooit. Elk element op de heap alloceren is killing voor performance op meerdere manieren. Neemt niet weg dat je linked-list-achtige structuren kan implementeren. Bv een contiguous vector storage met index references naar elementen, die kan je dan eens in de zoveel tijd opschonen.

[Soultaker]

Ik zou het niet zo strikt stellen. Op hele kleine embedded systemen alloceer je geheugen meestal van te voren, maar dat kan net zo goed met de elementen van een linked list als met een array. Je next-pointers komen dan overeen met indices in je array, maar het is veel makkelijker om een free-list bij te houden dan een secundaire array met indices die je ook nog moet opschonen om de zoveel tijd.

Op iets minder kleinere systemen waar je bijvoorbeeld Linux op kan draaien, is heap allocatie niet altijd bezwaarlijk. Je moet je vooral laten leiden door de vraag welke eigenschappen van de datastructuur je nodig hebt. Ten opzichte van een dynamische array heeft een linked list het voordeel dat elementen niet verplaatst hoeven worden als je elementen toevoegt of verwijdert (pointers naar elementen blijven altijd geldig), and dat de performance van operaties voorspelbaar is (je hoeft nooit de hele lijst te heralloceren als je één element toevoegt of verwijdert, wat fijn is als je bijvoorbeeld in een interrupt handler een element wil verwijderen).

In het concrete geval van de TS is een linked list ongeschikt omdat de benodigde eigenschappen (toevoegen en verwijderen van elementen op volgorde) niet efficiënt te implementeren zijn, maar dat betekent niet dat een linked list "eigenlijk nooit" geschikt is. Niet voor niets zit de Linux kernel bijvoorbeeld vol met linked lists.

[.oisyn]

Sissors schreef op zondag 13 december 2015 @ 23:12:
Dan is een priority queue inderdaad efficienter (effectief dus gewoon een array van tijden wanneer iets moet worden uitgevoerd + een pointer/ID of dat iets als ik het goed begrijp)

Een binary heap is een binary tree die opgeslagen is als array, waarbij de children van de node op index n staan op plekken n*2 en n*2+1, en zijn parent op n/2. De root staat dan typisch op index 1 (want dat rekent makkelijker, al kun je het prima aanpassen dat de root op 0 staat). De boom is verder altijd gebalanceerd, want er staan geen lege plekken in de array.

In het geval van een priority queue is het geen gesorteerde boom. De enige garantie die er is is dat de parent node altijd kleiner is dan zijn twee child nodes. Dit betekent automatisch dat een node het kleinste element is van zijn eigen deelboom, en dus dat de root het kleinste element van de gehele boom is. Bij het 'poppen' van het eerste element van de priority queue ontstaat er een gat (want je neemt de root weg), die wordt opgevuld door de kleinste van de twee children. Dan ontstaat daar weer een gat, etc. Insertion gaat op een vergelijkbare manier, je zet het element achteraan in de array en dan verwissel je 'm recursief met zijn ancestors als het nieuwe element kleiner is dan zijn parent. Vandaar dus O(log n) insertion en O(log n) extraction.

Het lijkt me niet dat je snel meer dan een stuk of 10 elementen zal hebben hier.

Vandaar dat ik mijn voorlaatste opmerking nog veel essentieler vindt dan performance in dit geval - als je al beschikt over een datastructuur die exact doet wat je wilt, waarom zou je dan een generiekere datastructuur gebruiken waar je de gewenste logica (namelijk het gesorteerd zijn) zelf er nog omheen moet bouwen?

Maar goed, we hebben het hier natuurlijk wel over C, de taal zonder enige standaard containers whatsoever

[CurlyMo]

Aha, net even deze video gekeken en nu komt de clue binnen. Waar je denkt dat linked lists mooi lineair zijn, vragen ze eigenlijk een grote bulk aan random reads van je geheugen aangezien elke next pointer binnen de linked list naar een willekeurig ander geheugenblok wijst. Waar je denk dat je bij een vector / array moeilijker kan manipuleren en zoeken, ligt alles wel netjes in het geheugen waardoor het werken met een array vrijwel altijd sneller is. Ondanks het (hypothetisch) moeten verplaatsen van duizenden elementen bij het verwijderen van een element aan het begin.

[Soultaker]

.oisyn schreef op maandag 14 december 2015 @ 10:29:
Maar goed, we hebben het hier natuurlijk wel over C, de taal zonder enige standaard containers whatsoever

POSIX heeft tenminste nog search.h (Ja ja, is niet "standaard C".)