[Python] Lightweight non-blocking scheduler

[Possstema]

Voor dat ik mijn probleem aan jullie voorleg, zal ik even uitleggen wat ik probeer te maken.

Project
Er moet een server komen die voor mensen kan inloggen op een IMAP server die PUSH (het IDLE commando) ondersteund. Deze push berichten kunnen dan worden doorgesluisd naar een ander protocol die de gebruikers op de hoogte stelt van de wijzigingen. Uiteraard wil ik dit zo efficient mogelijk maken, dus een thread per connectie is onacceptabel. Nu hebben we daarvoor de select() call, welke heel mooi wordt gebruikt in de asyncore module van Python. Één van de onderdelen van het IDLE commando, is dat deze elke 30 minuten opnieuw moet worden aangemeld. Ik moet dus per connectie gaan bijhouden wanneer het IDLE commando opnieuw moet worden verzonden.

Probleem
Het bijhouden van wanneer het IDLE commando opnieuw moet worden verzonden kan in Python met threading.Timer, maar dat ben ik weer een Thread per connectie kwijt, en dat kost weer veel resources.

Ideëen
Een mogelijkheid die ik zelf bedacht had was 1 Thread waar alle connecties in een lijst komen te staan, gegroepeerd per minuut. Deze thread kijkt dan elke minuut welke connecties er moeten worden vernieuwd, en voert dit dan uit. Mijn grootste bezwaar hierbij, is dat met bijvoorbeeld 10000 connecties, er eens per minuut meer dan 300 commando's achter elkaar worden verstuurd. Erg onregelmatig dus.

Andere mogelijkheden zijn het Twisted framework. Als ik het goed begrepen heb is het een framework waarmee je een soort event-driven programma's kunt schrijven. Helaas is dit weer niet platform onafhankelijk. En ook wil ik juist zo'n min mogelijk code gebruiken voor de server. De IMAP client heb ik dan ook zelf geschreven in plaat van een module te gebruiken.

Een andere oplossing is het gebruik van microthreads. Dit kan m.b.v. Stackless Python. Maar dit is weer een complete Python interpreter, welke nog experimenteel is ook.

Het liefst doe ik het natuurlijk zoals signal.alarm, of zoals ObjC volgens mij kan. Max 1 thread die gewoon voor de timers zorgt, en de bijbehorende functies aanroept.

[Niemand_Anders]

Heb je al eens naar XMPP (Jabber) gekeken. Een IMAP server misbruiken lijkt mij niet de juiste oplossing. Je kunt ook een observer pattern inplementeren waarbij je de (client) connecties als observers gebruikt.

Maar om wat voor berichten (commando's) gaat het? En als er daadwerkelijk 10000 connecties met een high volume load komt, dan ontkom je er niet aan om het distributed te schrijven omdat je anders een scalability van niks hebt.

[Zoijar]

Je kan die lijst gesorteerd bijhouden/delen in een aparte thread, en die laten sleepen tot het volgende item klaar is. Hoewel je waarschijnlijk liever gewoon elke loop iteratie alle items verwerkt die nodig zijn, omdat je dan alles volledig single threaded kan houden.

[Possstema]

Niemand_Anders schreef op dinsdag 07 juli 2009 @ 12:01:
Heb je al eens naar XMPP (Jabber) gekeken. Een IMAP server misbruiken lijkt mij niet de juiste oplossing. Je kunt ook een observer pattern inplementeren waarbij je de (client) connecties als observers gebruikt.

Het gaat juist om de IMAP server waar ik de email-adressen aanmeld, het doorgeven naar gebruikers zelf gaat via een ander (eigen) protocol.

Maar om wat voor berichten (commando's) gaat het? En als er daadwerkelijk 10000 connecties met een high volume load komt, dan ontkom je er niet aan om het distributed te schrijven omdat je anders een scalability van niks hebt.

Het gaat dus daadwerkelijk om email-berichten. Heb overigens niet heel veel ervaring met distributed programming, maar had het idee om een soort loadbalancer te schrijven die de connecties gewoon verdeeld. Maar voorlopig hoeft dat denk ik nog niet

[Possstema]

Zoijar schreef op dinsdag 07 juli 2009 @ 12:05:
Je kan die lijst gesorteerd bijhouden/delen in een aparte thread, en die laten sleepen tot het volgende item klaar is. Hoewel je waarschijnlijk liever gewoon elke loop iteratie alle items verwerkt die nodig zijn, omdat je dan alles volledig single threaded kan houden.

Ik wil ook tijdens het loopen connecties kunnen toevoegen. Maar misschien kan het wel gewoon met een synchronized Queue, gezien alle timers toch 29 minuten zijn. Dus in princiepe komt elke nieuwe timer na alle timers in de Queue. Even uitdenken . Ik vraag me alleen wel af of dit niet misgaat met heel veel connecties?

[ Voor 14% gewijzigd door Possstema op 07-07-2009 12:13 ]

[Confusion]

Possstema schreef op dinsdag 07 juli 2009 @ 11:48:
En ook wil ik juist zo'n min mogelijk code gebruiken voor de server.

Dat is nogal een beperkende factor. Waarom wil je dat? Heb je weinig opslagruimte of geheugenruimte of is het puur als uitdaging?

Heb je http://docs.python.org/library/asyncore.html al gezien? Is dat niet een voldoende oplossing om desnoods 100000 connections af te handelen?

[Possstema]

Confusion schreef op dinsdag 07 juli 2009 @ 13:54:
[...]

Dat is nogal een beperkende factor. Waarom wil je dat? Heb je weinig opslagruimte of geheugenruimte of is het puur als uitdaging?

Puur als uitdaging. Het is meer dat ik geen externe bibliotheken wil gebruiken, omdat die (naar mijn idee) langzamer zijn dan een eigen specifieke implementatie.

Heb je http://docs.python.org/library/asyncore.html al gezien? Is dat niet een voldoende oplossing om desnoods 100000 connections af te handelen?

Zie startpost :

[...] Nu hebben we daarvoor de select() call, welke heel mooi wordt gebruikt in de asyncore module van Python. [...]

Het gaat dus vooral om de timers die de IDLE commando's opnieuw versturen na 29 minuten.

[Possstema]

Ik heb het . Hierbij moet er wel vanuit worden gegaan dat elke nieuwe timer later moet worden uitgevoerd dan de timers in de queue, maar gezien ze bij mij allemaal de zelfde tijd hebben is dat geen probleem:

Python:

import threading, time, Queue

class Scheduler(threading.Thread):
    def __init__(self):
        # Init Super
        threading.Thread.__init__(self)
        
        # Init queue
        self.queue = Queue.Queue()
        
        # Start
        self.start()
        
    def run(self):
        while True:
            t = self.queue.get()        # Get next time
            r = t[0] - time.time()      # Calculate remaining time
            if r > 0: time.sleep(r)     # Sleep till time
            t[1]()                      # Execute function

    def add(self, ti, fn):
        self.queue.put((time.time() + ti, fn))

[farlane]

Possstema schreef op dinsdag 07 juli 2009 @ 14:40:
Het gaat dus vooral om de timers die de IDLE commando's opnieuw versturen na 29 minuten.

Timers? Ik neem toch aan dat je 1 loop gebruikt om meerdere verbindingen te checken?

code:

for each Connection in Connections
    if GetTick - Connection.LastTick > 30 minuten
        Connection.LastTick = GetTick
        Connection.SendIdle
    endif
next

[Remus]

farlane schreef op dinsdag 07 juli 2009 @ 15:10:
[...]

Timers? Ik neem toch aan dat je 1 loop gebruikt om meerdere verbindingen te checken?

code:

for each Connection in Connections
    if GetTick - Connection.LastTick > 30 minuten
        Connection.LastTick = GetTick
        Connection.SendIdle
    endif
next

Dat is dus een voorbeeld van een busy-loop wat nogal kostbaar is. Misschien is het een idee om een sorted tree (geloof ik, mijn datastructuren zijn een beetje weggezakt) te gebruiken waarbij gesorteerd wordt op de deadline tijd. Dan is het een kwestie van de eerste item uit de tree halen, wachten tot de deadline tijd, uitvoeren, deadline tijd wijzigen en opnieuw inserten en de volgende ophalen.

Overigens stelt RFC2177 (IMAP4 IDLE) dat het aanbovelen is om een client minimaal iedere 29 het IDLE commando te beeindigen (met DONE) en opnieuw uit te voeren en dat een server na 30 minuten de verbinding mag verbreken (impliciet of expliciet!). Je zou dus ook kunnen overwegen om gewoon de minimale deadline te bepalen en dan voor alle verbindingen DONE en IDLE te versturen en de deadline voor alle verbindingen 29 minuten (of minder) in de toekomst te zetten.

[ Voor 22% gewijzigd door Remus op 07-07-2009 16:00 ]

[Possstema]

Remus schreef op dinsdag 07 juli 2009 @ 15:53:
[...]


Dat is dus een voorbeeld van een busy-loop wat nogal kostbaar is. Misschien is het een idee om een sorted tree (geloof ik, mijn datastructuren zijn een beetje weggezakt) te gebruiken waarbij gesorteerd wordt op de deadline tijd. Dan is het een kwestie van de eerste item uit de tree halen, wachten tot de deadline tijd, uitvoeren, deadline tijd wijzigen en opnieuw inserten en de volgende ophalen.

Overigens stelt RFC2177 (IMAP4 IDLE) dat het aanbovelen is om een client minimaal iedere 29 het IDLE commando te beeindigen (met DONE) en opnieuw uit te voeren en dat een server na 30 minuten de verbinding mag verbreken (impliciet of expliciet!). Je zou dus ook kunnen overwegen om gewoon de minimale deadline te bepalen en dan voor alle verbindingen DONE en IDLE te versturen en de deadline voor alle verbindingen 29 minuten (of minder) in de toekomst te zetten.

Dat doe ik dus nu (volgens mij). fn wordt namelijk aangeroepen na 29 minuten, welke het DONE commando stuurt, en opnieuw IDLE aanvraagt.

Edit: Oh, wacht... Ik denk dat ik je verkeert heb begrepen... Je wilt dat ik gewoon iedereen tegelijk het IDLE command toestuur, in de tijd van de eerste socket. Dat lijkt me niet zo handig, al helemaal niet als er heel veel connecties zijn. Ze worden namelijk ook willekeurig aangemaakt.

[ Voor 11% gewijzigd door Possstema op 07-07-2009 16:28 ]

[Remus]

Possstema schreef op dinsdag 07 juli 2009 @ 16:18:
[...]

Dat doe ik dus nu (volgens mij). fn wordt namelijk aangeroepen na 29 minuten, welke het DONE commando stuurt, en opnieuw IDLE aanvraagt.

Edit: Oh, wacht... Ik denk dat ik je verkeert heb begrepen... Je wilt dat ik gewoon iedereen tegelijk het IDLE command toestuur, in de tijd van de eerste socket. Dat lijkt me niet zo handig, al helemaal niet als er heel veel connecties zijn. Ze worden namelijk ook willekeurig aangemaakt.

Uiteindelijk gaat de cyclus voor alle verbindingen gelijk lopen (binnen 29 minuten na opzetten van de verbinding) . Het is misschien voor veel verbindingen niet het meest handige in verband met de seriele uitvoering, maar het is wel makkelijk uit te voeren.
Ik denk dat je anders toch moet gaan voor mijn andere suggestie van een sorted tree. In mijn vorige reactie was die overigens wel blocking. Als je die nonblocking wil dan moet je dus na controle dat de deadline nog niet bereikt is gewoon opnieuw inserten in de tree en dan iets anders afhandelen (ophalen IDLE boodschappen van de IMAP-server bijvoorbeeld ) en dan opnieuw de tree bevragen.

[Confusion]

Possstema schreef op dinsdag 07 juli 2009 @ 14:40:
Puur als uitdaging. Het is meer dat ik geen externe bibliotheken wil gebruiken, omdat die (naar mijn idee) langzamer zijn dan een eigen specifieke implementatie.

Je geeft twee onafhankelijke antwoorden. Mijn reactie op de tweede is: eerst een oplossing bouwen die werkt, daarna kijken of het snel genoeg is. Als het te langzaam is, bepalen welk onderdeel er te langzaam is. Daarna pas trage libraries verwijderen. Tien bestaande wielen opnieuw uitvinden, met de kans dat je bij ieder wiel in een valkuil tuimelt die de schrijvers van de library inmiddels ontweken hebben, is zonde van je tijd.

Als het puur een uitdaging is: prima natuurlijk, maar dat kan weleens aardig wat tijd gaan kosten. Hou vooral goed in de gaten of je niet regelmatig denkt "hmmm, ik heb ook nog dit-en-dit nodig', waarbij dit-en-dit in een van de ongebruikte libraries zit. Als je dat vaak genoeg hebt en je effectief de library aan het herimplementeren bent, dan kom je waarschijnlijk trager en met meer code uit, omdat mensen die er meer tijd in hebben gestoken vaak al vrij goede code geproduceerd hebben.

Overigens, als snelheid en multithreading echt belangrijk zijn, dan win je er misschien meer mee om naar Jython te kijken.

[ Voor 5% gewijzigd door Confusion op 07-07-2009 17:05 ]

[BartV]

Je wilt dus eigenlijk een grote hoeveelheid timeouts managen. Ik heb dit ooit gedaan (in C++) met behulp van 1 os-timer, en een geschikt tree-algorithme, bijvoorbeeld AVL tree.
Op het moment dat je een nieuwe timeout toevoegd, kijk je of deze eerder komt dan de eerste in de tree. Zo ja, voeg je hem toe en zet je de os-timer op de nieuwe dichtsbijzijnde timeout.
Als de os-timer fired, kijk je in de tree welke timeout daarbij hoort, en kan je die afhandelen. Hierna zet je de timer weer op de eerstvolgende timeout.

Ik heb zelf nauwelijk ervaring in Python, dus ik kan je niet vertellen of dit makkelijk te realiseren is.

[Possstema]

Confusion schreef op dinsdag 07 juli 2009 @ 17:04:
[...]

Je geeft twee onafhankelijke antwoorden. Mijn reactie op de tweede is: eerst een oplossing bouwen die werkt, daarna kijken of het snel genoeg is. Als het te langzaam is, bepalen welk onderdeel er te langzaam is. Daarna pas trage libraries verwijderen. Tien bestaande wielen opnieuw uitvinden, met de kans dat je bij ieder wiel in een valkuil tuimelt die de schrijvers van de library inmiddels ontweken hebben, is zonde van je tijd.

Klopt, de 2 staan redelijk los van elkaar, maar vooral in het geval van IMAP weet ik vrij zeker dat mijn implementatie efficienter is, vooral met 1000 connecties, dankzij het gebruik van select(). De standaard IMAP lib is bedoeld voor 1 connectie. Verder probeer ik het gebruik van bibliotheken meer te vermijden.

Als het puur een uitdaging is: prima natuurlijk, maar dat kan weleens aardig wat tijd gaan kosten. Hou vooral goed in de gaten of je niet regelmatig denkt "hmmm, ik heb ook nog dit-en-dit nodig', waarbij dit-en-dit in een van de ongebruikte libraries zit. Als je dat vaak genoeg hebt en je effectief de library aan het herimplementeren bent, dan kom je waarschijnlijk trager en met meer code uit, omdat mensen die er meer tijd in hebben gestoken vaak al vrij goede code geproduceerd hebben.

Overigens, als snelheid en multithreading echt belangrijk zijn, dan win je er misschien meer mee om naar Jython te kijken.

Is Jyhton niet langzamer dan Python? Ik dacht dat het meer handig was als je van de Java bibliotheek gebruik wou maken. Overigens is snelheid vrij belangrijk, maar als python het niet meer aan kan ga ik het misschien in c++ schrijven.

[Possstema]

Remus schreef op dinsdag 07 juli 2009 @ 16:51:
[...]


Uiteindelijk gaat de cyclus voor alle verbindingen gelijk lopen (binnen 29 minuten na opzetten van de verbinding) . Het is misschien voor veel verbindingen niet het meest handige in verband met de seriele uitvoering, maar het is wel makkelijk uit te voeren.
Ik denk dat je anders toch moet gaan voor mijn andere suggestie van een sorted tree. In mijn vorige reactie was die overigens wel blocking. Als je die nonblocking wil dan moet je dus na controle dat de deadline nog niet bereikt is gewoon opnieuw inserten in de tree en dan iets anders afhandelen (ophalen IDLE boodschappen van de IMAP-server bijvoorbeeld ) en dan opnieuw de tree bevragen.

Denk het toch niet. Stel je krijgt connecties binnen op min 5, 14, 25 en 35. Dan is de queue volgens mij zo:

code:

5           => klaar -> 5 + 29 toevoegen = 34
14          => klaar -> 14 + 29 toevoegen = 43
25          => klaar -> 25 + 29 toevoegen = 54
34 (van 5)  => klaar -> 34 + 29 toevoegen = 63
35          => klaar -> 35 + 29 toevoegen = 64
43 (van 14) => etc...

De afstanden tussen de timers blijft dus (ongeveer) gelijk.

[Possstema]

DikkieDik schreef op dinsdag 07 juli 2009 @ 17:08:
Je wilt dus eigenlijk een grote hoeveelheid timeouts managen. Ik heb dit ooit gedaan (in C++) met behulp van 1 os-timer, en een geschikt tree-algorithme, bijvoorbeeld AVL tree.
Op het moment dat je een nieuwe timeout toevoegd, kijk je of deze eerder komt dan de eerste in de tree. Zo ja, voeg je hem toe en zet je de os-timer op de nieuwe dichtsbijzijnde timeout.
Als de os-timer fired, kijk je in de tree welke timeout daarbij hoort, en kan je die afhandelen. Hierna zet je de timer weer op de eerstvolgende timeout.

Ik heb zelf nauwelijk ervaring in Python, dus ik kan je niet vertellen of dit makkelijk te realiseren is.

Dat was een beetje het probleem, volgens mij is er niet zo'n timer in Python die je zo makkelijk even aanpast.

[farlane]

Remus schreef op dinsdag 07 juli 2009 @ 15:53:
Dat is dus een voorbeeld van een busy-loop wat nogal kostbaar is. Misschien is het een idee om een sorted tree (geloof ik, mijn datastructuren zijn een beetje weggezakt) te gebruiken waarbij gesorteerd wordt op de deadline tijd. Dan is het een kwestie van de eerste item uit de tree halen, wachten tot de deadline tijd, uitvoeren, deadline tijd wijzigen en opnieuw inserten en de volgende ophalen.

Natuurlijk zou je dit kunnen optimaliseren, maar ik ga ervan uit dat er in die loop nog meer administratie gaat worden afgehandeld. ( Zoals het verwijderen van connections die verdwenen zijn etc )

Bij hoeveel elementen in je lijst zou het een probleem gaan opleveren denk je?

[Remus]

Possstema schreef op dinsdag 07 juli 2009 @ 18:26:
[...]

Denk het toch niet. Stel je krijgt connecties binnen op min 5, 14, 25 en 35. Dan is de queue volgens mij zo:

code:

5           => klaar -> 5 + 29 toevoegen = 34
14          => klaar -> 14 + 29 toevoegen = 43
25          => klaar -> 25 + 29 toevoegen = 54
34 (van 5)  => klaar -> 34 + 29 toevoegen = 63
35          => klaar -> 35 + 29 toevoegen = 64
43 (van 14) => etc...

De afstanden tussen de timers blijft dus (ongeveer) gelijk.

Volgens mijn plan wordt het:

code:

timeouts = {5, 14, 25}
eerste timeout: 5
beëindigen IDLE en verzenden nieuwe IDLE voor alle verbindingen
timeouts = {34, 34, 34}
op tijdstip 25 komt er een nieuwe verbinding binnen, timeout: 54
timeouts = {34, 34, 34, 54}
tweede timeout: 34
beëindigen IDLE en verzenden nieuwe IDLE voor alle verbindingen
timeouts = {63, 63, 63, 63}
etc.

Je mag een IDLE op ieder willekeurig moment beëindigen en opnieuw opzetten. Er wordt (ivm standaard timeout van 30 minuten) aangeraden om dat op zijn minst iedere 29 minuten te doen.

farlane schreef op dinsdag 07 juli 2009 @ 19:03:
[...]


Natuurlijk zou je dit kunnen optimaliseren, maar ik ga ervan uit dat er in die loop nog meer administratie gaat worden afgehandeld. ( Zoals het verwijderen van connections die verdwenen zijn etc )

Bij hoeveel elementen in je lijst zou het een probleem gaan opleveren denk je?

Het verwijderen van connections is in principe geen probleem. Als ik mij goed herinner wordt bij alle IMAP implementaties de verbinding pas door de server verbroken (vanwege een timeout) als de IDLE wordt beëindigd met DONE, dan is het verwijderen van connections dus onderdeel van de IDLE-cyclus.

Ik heb geen idee voor hoeveel verbindingen dit goed zal gaan. Als het non-blocking gebeurt is het heel erg afhankelijk van wat er nog meer wordt gedaan.

Possstema schreef op dinsdag 07 juli 2009 @ 18:20:
[...]

Klopt, de 2 staan redelijk los van elkaar, maar vooral in het geval van IMAP weet ik vrij zeker dat mijn implementatie efficienter is, vooral met 1000 connecties, dankzij het gebruik van select(). De standaard IMAP lib is bedoeld voor 1 connectie. Verder probeer ik het gebruik van bibliotheken meer te vermijden.

Waarom wil je het wiel opnieuw uitvoeren door libraries te vermijden?

[...]
Is Jyhton niet langzamer dan Python? Ik dacht dat het meer handig was als je van de Java bibliotheek gebruik wou maken. Overigens is snelheid vrij belangrijk, maar als python het niet meer aan kan ga ik het misschien in c++ schrijven.

Ik meen dat Jython wel echt multithreaded is, terwijl Python (C-python) dat niet is doordat er voor veel handelingen gebruik wordt gemaakt van de GIL (Global Interpreter Lock) waardoor zelfs zaken die multithreaded zijn opgezet effectief geserialiseerd worden. Dat fenomeen is bij Jython - voor zover ik weet - niet aanwezig. Daarnaast is het schrijven in C++ van de onderliggende VM van Python nog geen garantie voor snelheid.

[ Voor 50% gewijzigd door Remus op 07-07-2009 19:27 ]

[BartV]

Possstema schreef op dinsdag 07 juli 2009 @ 18:27:
[...]

Dat was een beetje het probleem, volgens mij is er niet zo'n timer in Python die je zo makkelijk even aanpast.

Aan wat ik zo snel hier zie: http://docs.python.org/library/signal.html lijkt er in Python 2.6 wel zo'n soort timer aanwezig. Er zitten wel wat mitsen en maaren aan het gebruik van signals en threads tegelijk, maar het is misschien een aardig uitgangspunt.

[ Voor 15% gewijzigd door BartV op 07-07-2009 23:40 ]

[Elijan9]

@Topicstarter:
Stackless Python is zeker niet meer "experimenteel" en deze Python interpreter is slecht op een paar punten gepatched om stackless te kunnen ondersteunen... O.a. EVE Online gebruikt het, en bij Hyves ook trouwens. Naar mijn mening alles behalve "experimenteel".

Mocht je stackless willen gaan gebruiken, er staat al een bijna compleet voorbeeld op: http://www.stackless.com/wiki/Idioms onder "Sleeping".

[supakeen]

Threads in Python zijn helaas erg slecht, het algemene advies luidt dan ook om ze niet te gebruiken. Vanaf 2.6 kun je gebruikmaken van de multiprocessing module welke dezelfde API als threading ondersteunt

Verder kun je vast wel flink multiplexen over je verbindingen eventueel i.c.m. Twisted.

Verder is het niet gebruiken van Twisted vanwege het ’zo min mogelijk code gebruiken’ natuurlijk eigenlijk stom. Twisted bestaat al jaren, en is algemeen geaccepteerd in de Python-cultuur. Ook is het zelf schrijven van modules die je eigenlijk al bijgeleverd worden natuurlijk niet heel effectief, je zegt dat het hier om snelheid gaat? Heb je al eens gekeken met timeit, cProfile enzo of je wel echt een verbetering hebt? Is al je zelfgeschreven code threadsafe? Zijn de libraries die je gebruikt dat, allemaal kleine puntjes om naar te kijken

[supakeen]

Als ook, ik hoor net dat Kamaelia (http://www.kamaelia.org/Home) Wel iets heeft op dit gebied!

[Elijan9]

ikanobori schreef op woensdag 08 juli 2009 @ 13:45:
Threads in Python zijn helaas erg slecht, het algemene advies luidt dan ook om ze niet te gebruiken. Vanaf 2.6 kun je gebruikmaken van de multiprocessing module welke dezelfde API als threading ondersteunt

ikanobori schreef op woensdag 08 juli 2009 @ 13:55:
Als ook, ik hoor net dat Kamaelia (http://www.kamaelia.org/Home) Wel iets heeft op dit gebied!

Stackless is naar mijn mening aanzienlijk sneller dan Kamaelia, zie ook bijvoorbeeld: http://entitycrisis.blogs...ackless-kamaelia-and.html

Stackless blijkt vrijwel altijd de beste oplossing te zijn als het gaat om het draaien met veel threads in Python. Overigens is "multiprocessing" in python 2.6 in veel gevallen tergend traag, vaak nog trager dan threads als er veel gecommuniceerd moet worden tussen de processen... Ik zou ook zeker niet aanbevelen om veel meer processen te draaien dan het aantal processor cores waar het op draait. Naar mijn mening loont "multiprocessing" alleen maar wanneer je minimaal 4 cores hebt, of als je echt last hebt van de Global Interpretor Lock. Bij twee cores is het vrijwel altijd sneller om threads te gebruiken.

[Possstema]

farlane schreef op dinsdag 07 juli 2009 @ 19:03:
[...]

Natuurlijk zou je dit kunnen optimaliseren, maar ik ga ervan uit dat er in die loop nog meer administratie gaat worden afgehandeld. ( Zoals het verwijderen van connections die verdwenen zijn etc )

Bij hoeveel elementen in je lijst zou het een probleem gaan opleveren denk je?

Connecties verdwijnen er niet zo veel. Ik heb 2 connectie-select-loops: 1 voor de inkomende aanmeldingen, welke in princiepe binnen enkele seconde weer verbroken zijn, en de verbindingen met de IMAP servers. Deze zal gemakkelijk een paar duizend verbindingen (moeten) kunnen bevatten.

Voor de duidelijk, dit probeer ik ongeveer te maken: http://www.iphoneclub.nl/...push-gmail-voor-iedereen/. Helaas zijn ze me voor, maar het blijft een leuk project om veel van te kunnen leren.

offtopic:
Excuses voor de late reacties. Had even een weekje studie ingepland. Zal proberen op iedereen even te reageren.

[Possstema]

Remus schreef op dinsdag 07 juli 2009 @ 19:11:
[...]
Volgens mijn plan wordt het:

code:

timeouts = {5, 14, 25}
eerste timeout: 5
beëindigen IDLE en verzenden nieuwe IDLE voor alle verbindingen
timeouts = {34, 34, 34}
op tijdstip 25 komt er een nieuwe verbinding binnen, timeout: 54
timeouts = {34, 34, 34, 54}
tweede timeout: 34
beëindigen IDLE en verzenden nieuwe IDLE voor alle verbindingen
timeouts = {63, 63, 63, 63}
etc.

Je mag een IDLE op ieder willekeurig moment beëindigen en opnieuw opzetten. Er wordt (ivm standaard timeout van 30 minuten) aangeraden om dat op zijn minst iedere 29 minuten te doen.

Toch lijkt me het handiger dat de calls verspreid blijven. Volgens mij wil je niet elk half uur 5000 berichten de deur uit doen, terwijl je de overige tijd relatief weinig te doen hebt.

[...]

Het verwijderen van connections is in principe geen probleem. Als ik mij goed herinner wordt bij alle IMAP implementaties de verbinding pas door de server verbroken (vanwege een timeout) als de IDLE wordt beëindigd met DONE, dan is het verwijderen van connections dus onderdeel van de IDLE-cyclus.

Ik heb geen idee voor hoeveel verbindingen dit goed zal gaan. Als het non-blocking gebeurt is het heel erg afhankelijk van wat er nog meer wordt gedaan.


[...]


Waarom wil je het wiel opnieuw uitvoeren door libraries te vermijden?

Om even een misverstand de wereld uit te helpen, ik ben absoluut niet tegen libraries, integendeel, ik gebruik ze het liefst zo veel mogelijk. Maar in het geval van de IMAP library van python, gebruikt deze voor elke connectie een Thread, wat volgens mij in mijn geval erg onhandig is. Ook omdat ik IMAP niet helemaal gebruik waarvoor het bedoeld is ('mail ophalen' vs. 'luisteren of er nieuwe mail is') kan ik een aantal efficientie-keuzes maken die je normaal niet kan veroorloven.

[...]


Ik meen dat Jython wel echt multithreaded is, terwijl Python (C-python) dat niet is doordat er voor veel handelingen gebruik wordt gemaakt van de GIL (Global Interpreter Lock) waardoor zelfs zaken die multithreaded zijn opgezet effectief geserialiseerd worden. Dat fenomeen is bij Jython - voor zover ik weet - niet aanwezig. Daarnaast is het schrijven in C++ van de onderliggende VM van Python nog geen garantie voor snelheid.

[Possstema]

DikkieDik schreef op dinsdag 07 juli 2009 @ 23:38:
[...]

Aan wat ik zo snel hier zie: http://docs.python.org/library/signal.html lijkt er in Python 2.6 wel zo'n soort timer aanwezig. Er zitten wel wat mitsen en maaren aan het gebruik van signals en threads tegelijk, maar het is misschien een aardig uitgangspunt.

Je hebt gelijk. Mijn fout. Helaas kan alleen de hoofd-thread het signal ontvangen. Uiteraard kan je dat wel weer doorgeven aan de desbetreffende thread, maar dat zal vast weer een aantal problemen met zich meebrengen. Is dat wat je bedoeld met de mitsen en maaren?

[Possstema]

Elijan9 schreef op woensdag 08 juli 2009 @ 10:00:
@Topicstarter:
Stackless Python is zeker niet meer "experimenteel" en deze Python interpreter is slecht op een paar punten gepatched om stackless te kunnen ondersteunen... O.a. EVE Online gebruikt het, en bij Hyves ook trouwens. Naar mijn mening alles behalve "experimenteel".

Mocht je stackless willen gaan gebruiken, er staat al een bijna compleet voorbeeld op: http://www.stackless.com/wiki/Idioms onder "Sleeping".

Kreeg idd het idee dat Stackless al wel prima stabiel was, alleen zie het voordeel van stackless-threads t.o.v. een select loop nog niet helemaal. Lijkt me dat je nog steeds *iets* van overhead hebt. En daarnaast, je kunt niet meer van de standaard Python interpreter gebruik maken. Vind ik toch een redelijk nadeel.

offtopic:
Overigens is Hyves niet het ideale voorbeeld van efficiënt programmeren , maar dat terzijde. Ze zijn laatst bij ons op de universiteit geweest, bizar hoeveel servers ze gebruiken!

[Possstema]

ikanobori schreef op woensdag 08 juli 2009 @ 13:45:
Threads in Python zijn helaas erg slecht, het algemene advies luidt dan ook om ze niet te gebruiken. Vanaf 2.6 kun je gebruikmaken van de multiprocessing module welke dezelfde API als threading ondersteunt

Verder kun je vast wel flink multiplexen over je verbindingen eventueel i.c.m. Twisted.

Verder is het niet gebruiken van Twisted vanwege het ’zo min mogelijk code gebruiken’ natuurlijk eigenlijk stom. Twisted bestaat al jaren, en is algemeen geaccepteerd in de Python-cultuur. Ook is het zelf schrijven van modules die je eigenlijk al bijgeleverd worden natuurlijk niet heel effectief, je zegt dat het hier om snelheid gaat? Heb je al eens gekeken met timeit, cProfile enzo of je wel echt een verbetering hebt? Is al je zelfgeschreven code threadsafe? Zijn de libraries die je gebruikt dat, allemaal kleine puntjes om naar te kijken

Niets is stom, hoogstens niet slim, of onhandig. En ja, de eigen code is thread-safe. Er zijn maar 5 threads die allemaal hun eigen domein hebben. De enige communicatie gebeurt d.m.v. de queue.Queue klasse, welke juist bedoelt is voor thread-communicatie. Zal binnenkort wel eens even een profiling tool erover heen gooien, ben wel erg benieuwd .

[Possstema]

Elijan9 schreef op woensdag 08 juli 2009 @ 14:45:
[...]


[...]

Stackless is naar mijn mening aanzienlijk sneller dan Kamaelia, zie ook bijvoorbeeld: http://entitycrisis.blogs...ackless-kamaelia-and.html

Stackless blijkt vrijwel altijd de beste oplossing te zijn als het gaat om het draaien met veel threads in Python. Overigens is "multiprocessing" in python 2.6 in veel gevallen tergend traag, vaak nog trager dan threads als er veel gecommuniceerd moet worden tussen de processen... Ik zou ook zeker niet aanbevelen om veel meer processen te draaien dan het aantal processor cores waar het op draait. Naar mijn mening loont "multiprocessing" alleen maar wanneer je minimaal 4 cores hebt, of als je echt last hebt van de Global Interpretor Lock. Bij twee cores is het vrijwel altijd sneller om threads te gebruiken.

Heb nu max 6 threads, waarvan er eigenlijk maar 2 iets doen. Dit aantal zal hoogstwaarschijnlijk niet groter worden. De code moet op een dual-core of quad core komen te draaien. Is het dan nog steeds beter om het m.b.v. stackless threads te doen i.p.v. select/multiplexing?

[Remus]

Possstema schreef op vrijdag 17 juli 2009 @ 13:34:
Toch lijkt me het handiger dat de calls verspreid blijven. Volgens mij wil je niet elk half uur 5000 berichten de deur uit doen, terwijl je de overige tijd relatief weinig te doen hebt.

Dat wil ik ook niet ontkennen, maar het is wel heel erg simpel. Daarnaast: is het belangrijk of je heel erg spreidt of dat je alles aan een stuk door afhandelt? IMHO alleen als het een zware belasting oplevert en dat valt denk ik wel mee.

Om even een misverstand de wereld uit te helpen, ik ben absoluut niet tegen libraries, integendeel, ik gebruik ze het liefst zo veel mogelijk. Maar in het geval van de IMAP library van python, gebruikt deze voor elke connectie een Thread, wat volgens mij in mijn geval erg onhandig is. Ook omdat ik IMAP niet helemaal gebruik waarvoor het bedoeld is ('mail ophalen' vs. 'luisteren of er nieuwe mail is') kan ik een aantal efficientie-keuzes maken die je normaal niet kan veroorloven.

Op zich ging het mij meer om de volgende zin: Verder probeer ik het gebruik van bibliotheken meer te vermijden. Daaruit maakte ik eigenlijk op dat je in het algemeen geen libraries wilt gebruiken. Verder kan ik me voorstellen dat het prima mogelijk is om de IMAP library van Python op bepaalde punten te herbruiken.

Possstema schreef op vrijdag 17 juli 2009 @ 13:48:

offtopic:
Overigens is Hyves niet het ideale voorbeeld van efficiënt programmeren , maar dat terzijde. Ze zijn laatst bij ons op de universiteit geweest, bizar hoeveel servers ze gebruiken!

Hoe weet jij of ze wel of niet efficiënt programmeren? Alleen aan het externe gedrag kan je niet altijd afleiden of er wel of niet efficient geprogrammeerd is.
Je kan ook zeggen: bizar hoeveel gebruikers ze hebben

[Possstema]

Remus schreef op vrijdag 17 juli 2009 @ 15:38:
[...]


Dat wil ik ook niet ontkennen, maar het is wel heel erg simpel. Daarnaast: is het belangrijk of je heel erg spreidt of dat je alles aan een stuk door afhandelt? IMHO alleen als het een zware belasting oplevert en dat valt denk ik wel mee.

Zie de 8e post van dit topic, is toch ook heel simpel?

[...]

Op zich ging het mij meer om de volgende zin: Verder probeer ik het gebruik van bibliotheken meer te vermijden. Daaruit maakte ik eigenlijk op dat je in het algemeen geen libraries wilt gebruiken. Verder kan ik me voorstellen dat het prima mogelijk is om de IMAP library van Python op bepaalde punten te herbruiken.

Ja, ok, niet helemaal handig. Bedoel meer dat ik liever pas een bibliotheek gebruik als ik het niet anders kan oplossen, of het duidelijk makkelijker is. Bij de IMAP lib, daarbij kost het me een stuk meer moeite om uit te zoeken welke delen ik wel en niet kan gebruiken. Heb dat nu echt wel goed, geloof me .

[...]

Hoe weet jij of ze wel of niet efficiënt programmeren? Alleen aan het externe gedrag kan je niet altijd afleiden of er wel of niet efficient geprogrammeerd is.
Je kan ook zeggen: bizar hoeveel gebruikers ze hebben

Leid het ook niet af aan het externe gedrag. Ze hebben laatst een uitgebreide technische lezing gegeven bij ons op de uni, en dit was wel een beetje het hoofdthema, snelheid . Maar ze zijn zeker goed bezig om hier verandering in te brengen.

[Elijan9]

Possstema schreef op vrijdag 17 juli 2009 @ 13:56:
[...]

Heb nu max 6 threads, waarvan er eigenlijk maar 2 iets doen. Dit aantal zal hoogstwaarschijnlijk niet groter worden. De code moet op een dual-core of quad core komen te draaien. Is het dan nog steeds beter om het m.b.v. stackless threads te doen i.p.v. select/multiplexing?

offtopic:
Beetje late reactie, maar dat mag wel in de vakantietijd

Met zo weinig taken i.c.m. meerdere cores kun je beter multiprocessing gebruiken dan beide. Met weinig taken is de overhead voor multiprocessing minimaal en de winst van het op meerdere cores draaien groot. Met threads in python draai je praktisch altijd maar op 1 core (in verband met de beruchte Global Iterpreter Lock).

[Verwijderd]

Als je echt goed schalende code wilt zul je bijna haast wel moeten kijken naar threading oplossingen. 1 per connectie is mischien wat overdreven maar benchmarks met pthreads onder linux hebben wel uitgewezen dat 60.000 threads geen probleem zijn voor de OS scheduler. Je bent sneller uit IP poorten dan performance.

Grootste voordeel van een multi-threaded opzet is dat je bijna oneindig schaalt met meer cores. Een single threaded oplossing kan al snel tegen zijn limiet aanlopen vanwege amdale's law.

Maar goed als je het dan toch single threaded wilt/moet doen heb ik nog wel een idee. In plaats een tree te gebruiken zou je een circular buffer kunnen gebruiken. Je hebt 2 array's: 1 met de connecties die elke 29 minuten moeten refreshen om het zo maar even te zeggen en 1 array met 1800 indexes.

Als je een connectie hebt gemaakt/refreshed pak je de huidige time + 1740 modulus 1800 en plaats de connectie id onder die index in de circular buffer. Aan het begin van elke loop pak je de huidige time modulus 1800 en refreshed de connectie(s) onder die index. Je hebt zo geen enkele lookups, slechts wat integer rekenwerk en directe jumps. Sneller als dat wordt het niet ik weet alleen niet of python de mogelijkheid bied voor C/C++ style array's wat eigenlijk gewoon pointers naar directe geheugen lokaties zijn.

incomplete ongeteste C++/pseudo code

code:

conn Connecties[10000];
int Timer[1800];
conn CurrentCon;
int ConId;
int Current;
int Index;
int Next;

 while(true) {
  // Accepteer nieuwe connecties en voeg ze aan de Connecties array toe.

  if(time() > Current){
   Current = time();
   Index = Current % 1800;

   foreach(Timer[Index] as ConId){
    CurrentCon = Connecties[ConId];
     // Refresch CurrentCon

    Next = ((time() + 1740) % 1800);
    Timer[Next][] = ConId;
   }

   sleep(1);
  }
 }

Zoiets dus. Het is wel busy looping dus mischien is een die sleep(1) nog niet eens zo'n slecht idee. Indien je meer dan 1 seconden bezig bent om alle connecties voor die seconde te doen zal de index voor de volgende seconde(n) worden geskipped maar 30 minuten later alsnog worden afgehandeld aangezien die index gewoon blijft staan. Veel sneller als dit wordt het niet aangezien er geen enkele lookup is, alleen directe jumps en 4kb geheugen gebruik voor zo'n snelle scheduler is prima te overzien. Zelfs als je 640kb ram hebt

[Remus]

Verwijderd schreef op donderdag 30 juli 2009 @ 01:05:
Als je echt goed schalende code wilt zul je bijna haast wel moeten kijken naar threading oplossingen. 1 per connectie is mischien wat overdreven maar benchmarks met pthreads onder linux hebben wel uitgewezen dat 60.000 threads geen probleem zijn voor de OS scheduler. Je bent sneller uit IP poorten dan performance.

Grootste voordeel van een multi-threaded opzet is dat je bijna oneindig schaalt met meer cores. Een single threaded oplossing kan al snel tegen zijn limiet aanlopen vanwege amdale's law.

Dat is met Python niet zo, aangezien Python een zogenaamde Global Interpreter Lock heeft, waardoor zelfs meerdere threads effectief geserialiseerd worden (met uitzondering van sommige C-libraries die de GIL kunnen vrijgeven).

Verder is het dus niet zo dat multithreading oneindig schaalt. Er is altijd enige overhead van de scheduler en van het coordineren van data en andere thread-interacties. Zelfs als je dat tot een minimum weet te beperken is de schaalbaarheid niet lineair.

[Elijan9]

Verwijderd schreef op donderdag 30 juli 2009 @ 01:05:
Als je echt goed schalende code wilt zul je bijna haast wel moeten kijken naar threading oplossingen. 1 per connectie is mischien wat overdreven maar benchmarks met pthreads onder linux hebben wel uitgewezen dat 60.000 threads geen probleem zijn voor de OS scheduler.

Ja, maar bij Python is dat dus wel een probleem, Python threading is niet goed schalend, daar heb je al bij 1000 threads al problemen... Gelukkig zijn er ook alternatieven.

[Verwijderd]

Ik heb zelf nooit in Python geprogrammeerd maar je kunt dus eigenlijk gewoon zowat stellen dat Python geen echte multi-threading mogelijkheden heeft net zoals bijvoorbeeld PHP of JavaScript. Mijn punt was gewoon meer dat er onder Linux met POSIX Threads in C/C++ geen probleem is om 10.000 threads te hebben ivm overhead.

Mischien dat mijn post dan nog wel belangrijker was aangezien een snellere single-threaded scheduler kon ik zo even niet bedenken maar dan moet Python wel C-style arrays ondersteunen natuurlijk zonder verborgen lookups.