[Alg] Straight-Through Processing *

[Verwijderd]

Mede tweakers,

Een aantal vraagjes over een pogramma welke ik wil gaan ontwerpen en implementeren. Het betreft een programma welke continue data (via internet) feed krijgt (aandelen koersen + volumes etc). Hieraan wil ik algoritmes hangen waarmee realtime koop en verkoop signalen gegenereerd kunnen worden.

volgende overwegingen (graag jullie mening)
1 Mijn gedachte is om c++ te gebruiken (geschikt voor realtime programmeren) twijfelde om anders perl te gebruiken. Er moet veel data verwerkt worden én rekenwerk.

2 het gebruik van multi threads? De applicatie moet tenminste 40 aandelen in gaten kunnen houden (voor elk aandeel een thread). De main program ontvangt data en stuurt deze door naar de desbetreffende thread.
Ander mogelijkheid is om alles in "een" groot programma onder te brengen.

3 de algoritmes zal gebruik maken van history van een aandeel, verstandig om deze in een database onder te brengen of in het geheugen opslaan (in de vorm van array \ gelinkte lijst)? Mijn voorkeur gaat naar geheugen omdat de data snel toeganklijk moet zijn.

wacht met spanning af

Shao

[rashnu]

1. C++ is niet nodig de Pc's / servers van tegenwoordig kunnen genoeg aan. Hierdoor heb je binnen dit programma Niet echt de snelheid van C(++) nodig.

2. Waarom moeilijk doen wanneer het niet nodig is. De data die je binnen krijgt kan makkelijk door de proccesor verwerkt worden.

3. Array is goed maar ik zal het wel af en toe opslaan in een DB dit om een history op te bouwen. Wanneer je PC crasht wil je wel dat bijna alles is bewaard.(Toch?)

[.oisyn]

Rashnu schreef op 14 September 2003 @ 00:10:
1. C++ is niet nodig de Pc's / servers van tegenwoordig kunnen genoeg aan. Hierdoor heb je binnen dit programma Niet echt de snelheid van C(++) nodig.

just because you can doesn't mean you should
Bovendien moet je respect hebben voor de andere apps die draaien op het systeem. Leuk als het jouw app trekt, maar als er geen ruimte meer over is voor de rest dan is het ook niet echt fijn. Het verschil tussen 1 C++ app of 1 perl app boeit niet, maar doe diezelfde vergelijking tussen 10 C++ apps die naast elkaar draaien, en 10 perl apps die naast elkaar draaien.

Overigens moet je nadenken waar de bottleneck zit. Zijn het veel berekeningen, dan zou ik sowieso voor C++ gaan (niet alleen snelheid, maar gewoon algoritmen an sich zijn beter te implementeren in een native taal). Als het puur ligt aan de hoeveelheid data die binnenkomt maakt het natuurlijk niets uit. Dat is net zo snel in C++ als in perl (hoewel je in C++ (of elke andere native taal) toegang hebt tot features van het operating system, met name synchronization en asynchronous operations)

2. Waarom moeilijk doen wanneer het niet nodig is. De data die je binnen krijgt kan makkelijk door de proccesor verwerkt worden.

maar jij weet natuurlijk niet wat er gedaan moet worden, dus hoe kun je daar aannames over doen? (of kennen jullie elkaar? )
Anyway, het ligt een beetje aan wat je wilt doen. Het voordeel van multithreading is dat je geen tussentijdse states op hoeft te slaan zodat je verder kan met een andere berekening. Het nadeel is natuurlijk wel weer synchronization, wat soms een behoorlijke pain in the ass kan zijn (en het is moeilijk te debuggen).
Op multiprocessing systemen zorgt dit overigens wel weer voor een betere verdeling van de load

3. Array is goed maar ik zal het wel af en toe opslaan in een DB dit om een history op te bouwen. Wanneer je PC crasht wil je wel dat bijna alles is bewaard.(Toch?)

Idd, ik zou permanente opslag ook als backup nemen. Dus schrijf het wel weg, maar houd het ook in het geheugen. Je hebt het sowieso nodig, dus elke keer uit de database trekken, of uit een file halen, is een beetje nutteloos (misschien een caching systeem inbouwen, voor als het teveel geheugen gaat innemen?)

[Soultaker]

Onder real-time programming wordt in het algemeen verstaan, dat je programma gegarandeerd binnen bepaalde tijdsbeperkingen moet blijven. Het is niet synoniem met het "snel" verwerken van gegevens; voor jouw doeleinden lijkt me een gewoon vlot programma de bedoeling.

Ik weet niets van koersen en aandelen, dus ik kan niet beoordelen in hoeverre je de snelheid van C++ nodig hebt. Eventueel zou je een prototype kunnen schrijven in Perl en vervolgens, uitgaande van (bijvoorbeeld) een factor 5 verschil, nagaan of het zinnig is het programma te herschrijven in C++. Als je niet meer dan enkele duizenden berekeningen per seconde hoeft te doen, zou ik echter zeggen dat Perl wel geschikt genoeg is.

Multithreading is erg moeilijk om goed gebruik van te maken en het brengt op bepaalde punten ook weer performance overhead met zich mee. Gebruik het alleen als je zoveel mogelijk onafhankelijke taken hebt (die dus geen onderlinge synchronisatie vereisen), of als het het enige middel is om de beschikbare CPU-kracht efficient te benutten (op een multi-processor-systeem, bijvoorbeeld). In jouw geval kun je het monitoren van elk aandeel in een aparte thread stoppen, mits de koersen van de aandelen elkaar niet beïnvloeden. Als alle threads bij alle gegevens moeten kunnen, is multithreading misschien niet praktisch.

Hoe je de gegevens die je analyseert opslaat, hangt van twee dingen af: om hoeveel gegevens gaat het en hoe frequent worden gegevens opgevraagd? Ik kan dat, zonder verdere kennis van je algoritmen, niet beoordelen. Als je uitsluitend de gegevens van de laatste paar uur nodig hebt (en deze kun je binnentrekken via internet, dus echt ontzettend veel kan het niet zijn) en je hebt deze gegevens ook echt allemaal nodig, dan zou ik het gewoon in het geheugen houden. Mocht het niet passen, dan swapt je besturingssysteem de irrelevante gegevens wel naar de harde schijf.

edit:
@.oisyn: wil je ophouden met me elke keer vijf minuten voor zijn?!

[ Voor 4% gewijzigd door Soultaker op 14-09-2003 00:33 ]

[Verwijderd]

hmmm,

De reden dat multithreading in de picture komt is dat ik meerdere aandelen in de gaten moet houden. Elk data wat voor een bepaalt aandeel binnenkomt moet verwerkt worden en algortimes erop los gelaten worden (om data ruis eruit te filteren), denk aan fouriers etc. Dit kan je mooi in thread opsplitsen (per aandeel) ipv alles binnen een groot programma te draaien.

Een ander reden voor threads is omdat ik er een continue stroom van data is. Stel dat de programma aantal ms bezig is om de data op tijdstip T te verwerken, kan het zijn dat data de tijdstip T+1 met een delay verwerkt wordt... en dit is dan het einde van het realtime systeem. Met threads heb je dat niet....

Dat van tussentijds opslaan in een db is inderdaad een goed idee,...

enne ik geloof dat ik Rashnu niet persoonlijk ken

[.oisyn]

Mja, voor fourier transforms is perl dis echt NIET the right tool for the job

[Soultaker]

Verwijderd schreef op 14 September 2003 @ 00:38:
De reden dat multithreading in de picture komt is dat ik meerdere aandelen in de gaten moet houden. Elk data wat voor een bepaalt aandeel binnenkomt moet verwerkt worden en algortimes erop los gelaten worden (om data ruis eruit te filteren), denk aan fouriers etc. Dit kan je mooi in thread opsplitsen (per aandeel) ipv alles binnen een groot programma te draaien.

Dat is inderdaad de juiste beargumentering van een multi-threaded systeem. Omdat elke thread zich met één taak bezig houdt, wordt het bijhouden van je lokale staat eenvoudiger. Als bonus krijg je de fijnere graad van multiprocessing erbij kado.

Een ander reden voor threads is omdat ik er een continue stroom van data is. Stel dat de programma aantal ms bezig is om de data op tijdstip T te verwerken, kan het zijn dat data de tijdstip T+1 met een delay verwerkt wordt... en dit is dan het einde van het realtime systeem. Met threads heb je dat niet....

Dat is onzin; multi-threading helpt je niet om deadlines te halen. Je hebt geen enkele garantie over de tijd die je thread toegewezen krijgt; niet met een enkele thread en ook niet met meerdere.

Weet je zeker dat de berekening op de milliseconden aankomt? Ik kan me daar weinig bij voorstellen, namelijk. Is een statische performance (bijvoorbeeld een response binnen 100 milliseconde in >90% van de gevallen) niet genoeg?

Dat van tussentijds opslaan in een db is inderdaad een goed idee,...

enne ik geloof dat ik Rashnu niet persoonlijk ken

Je kunt niet gegevens uit een database halen en verwachten dat je responsetijden in de orde van enkele honderden milliseconden kunt halen. Je moet dus een afweging maken.

[Soultaker]

.oisyn schreef op 14 September 2003 @ 00:43:
Mja, voor fourier transforms is perl dis echt NIET the right tool for the job

Mwah, als het maar zo standaard is dat er een native Perl-module voor bestaat, is er niet echt een probleem. Je Perl script koppelt dan alleen wat native componenten aan elkaar en dat is snel zat. Als je daadwerkelijke Fourier analyses wilt programmeren, is C/C++ (of een andere systeemprogrammeringstaal) inderdaad een betere keuze.

[zakalwe]

Kun je misschien iets meer over de specifieke toepassing vertellen? Vooral over deze 'continuë informatiestroom', van welke bron komt dat?

In welke programeertalen heb je zelf ervaring? Wat is de externe druk op het project (wanneer moet het af etc?)?

Zo krijgen wij wat meer inzicht in de situatie...

[Verwijderd]

"continue data stroom" : Van een broker op internet kan ik tegen betaling live data feed van de beursvloer krijgen. Elk gesloten transactie (bijv koop en\of verkoop van aandelen) krijg ik tot mijn beschikking ("1000 aandelen koop asml op 13E"). Je kan je dan ook voorstellen dat elke seconde veel data verwerkt en ge-evalueerd moet worden.

Mijn programmeer ervaring bestaat uit MS VB 6.0 , C, C++, Perl
Het is een eigen project, mijn doel is om een autonome trading systeem te bouwen (tijdslijn is waarschijnlijk 9 mnd). Eerste insteek is om met mathematische modellen te proberen en later misschien met neurale netwerken.

over de opmerking van soultaker "multi-threading helpt je niet om deadlines te halen"
Ben ik volkomen mee eens, ik doelde meer op de volgende situatie
Alles zit in een groot programma: op tijdstip T komt de een transactie mbt asml binnen. Deze wordt direct verwerkt. Kort na tijdstip T (zeg halve seconde) komt een transactie mbt LogicaCMG binnen. Deze kan pas verwerkt worden als de data van asml is verwerkt.

Ingeval van een multithreaded systeem:
main krijgt dat van asml binnen,parsed deze door naar de thread asml en keert terug naar luister stand. Wanneer transactie LogicaCMG binnekomt dan wordt deze doorgeparsed naar thread LogicaCMG en keert terug naar luisterstand ..etc..

Wat betreft de hoeveelheid tijd voor de alg., dat weet ik (nog) niet. Moet eerst in kaart brengen welke ik wil gebruiken. Dat van Fourier was een voorbeeld, voor de kenners onder ons..ik wil waarschijnlijk wavelet transform gebruiken.

Ik weet het,...het wordt geen makkie... vooral het robuust maken van zo'n programma kost veel tijd. Ik wil nml niet dat er zometeen door een bug verkeerde aandelen worden gekocht

Daarom is alle commentaar,opmerkingen, tips welkom..

[ Voor 4% gewijzigd door Verwijderd op 14-09-2003 01:55 ]

[Skinkie]

mmm... waarom gaan mensen direct met moeilijke woorden als multithreads gooien terwijl het doel wat ze willen bereiken real time is... i think you missed the point. maar ik begrijp wel wat je wilt doen misschien kun je beter gaan multiplexen

[Soultaker]

Heb je toevallig een schatting van hoeveel gegevens je binnen denkt te krijgen? Hoeveel verschillende aandelen, hoeveel transacties per aandeel per seconde en hoeveel variatie op deze aantallen? Hoeveel vertraging is geoorloofd voor je reactie; ligt dat in de orde van enkele honderden milliseconden, of (tientallen) seconden?

[Verwijderd]

ik zal eerst een prescan doen van aandelen welke interessant zijn. Dit zal ongeveer 40 bedrijven zijn..

Wat betreft transacties, hier valt weinig pijl op te trekken. Soms is het heel "rustig" om 2 seconde een transactie totdat de bedrijf bijv winstcijfers bekend maakt dan gaat het heel rap. Denk aan meerdere transacties per seconde, de intervallen tussen deze transacties zullen ongeveer halve seconde is. Zat vorige week zes amerikaanse fondsen te monitoren (via de internet broker) totdat de macro cijfers bekendwaren, nou ik kan je vertellen dat ik in ieder geval de veranderingen niet meer bij kon houden. het ging echt snel.

En variatie per transactie van een aandeel... laat ik het anders zeggen "dit is bijna nooit hetzelfde".

Responstijd van zo'n trading systeem moet binnen aantal (lees 2) secondes zijn.

[ Voor 3% gewijzigd door Verwijderd op 14-09-2003 02:19 ]

[zakalwe]

Is het een autonoom systeem of komen er ook mensen aan te pas? Ik bedoel; maakt het systeem de beslissingen om aandelen te kopen of laat je dat via een interface over aan de gebruiker?
De reden dat ik deze (en onderstaande) vragen stel is dat het inzicht verschaft wat je voor de klanten van je systeem moet doen. Als het voor de klanten niet nodig is om elke 3 ms een aandelen order te kunnen verwerken hoef je het dus ook niet in de eerste versie te ontwikkelen.

Verdere vragen die jezelf kan stellen:

Wat is de doelgroep van je product? Hoe zouden zij het product graag willen gebruiken? Wat zijn de doelen en taken van een gebruiker van het systeem?

Welke concurrerende producten zijn er op de markt? Wat zijn de voor en nadelen van deze systemen? Wat is de meerwaarde van jouw toekomstige product ten opzichte van deze producten?

[MSalters]

Ik denk dat een multi-threaded oplossing nergens voor nodig is. Zoals gezegd, de state van een aandeel is met thread makkelijk te saven, maar ook zonder threads is dat uitstekend te doen. Als je een Fourier transformatie aan het uitvoeren bent, dan kun je inderdaad geen input lezen. Dat wil je ook niet, want je wilt eerst je Fourier transformatie afmaken. Die data zit in de cache, maak dat dan eerst af.

Multi-threading is hier alleen relevant als er prioriteiten zijn, dat je een fourier Transformatie van een onbelangrijk aandeel wil opschorten als er een belangrijker aandeel met informatie komt. Dan is het dus nuttig om de state van een onbelangrijke aandeel te saven. Multi-CPU lijkt voor het probleemdomein onnodig, dus dat wil je vermijden.

[Verwijderd]

Verdere vragen die jezelf kan stellen:

En een andere vraag die je jezelf misschien kan stellen is de rechtsgeldigheid van aankopen van je systeem (zijn er volgens de lokale wetgeving regels op het gedrag van je 'bot')?

[Verwijderd]

ik heb nog een beetje twijfels over het niet gebruiken van mulit threads, om in plaats daarvan states van aandelen op te slaan. Je krijg dan sequentiele verwerking van data...

Waar ik dan bang voor ben is dat het systeem niet in staat is om meerdere signalen simultaan te verwerken...systeem kan dan te laat reageren op relevante signalen. Dit zal alleen optreden als (worst case scenario) binnen een zeer kort tijdsbestek veel data binnenkomt.

Het programma zelf zal hoogstwaarschijnlijk nooit voor derde partij beschikbaar zijn. De enige gebruiker zal ikzelf zijn. Ik wil zo'n programma schrijven om mijn kunde te testen en natuurlijk wat geld ermee te verdienen (met handelen op de beurs)..

het programma moet zelfstandig orders kunnen inleggen en het is rechtsgeldig omdat ik een koop / verkoop order direct doorstuur naar de internet broker en deze ondersteund dit.

[farlane]

Verwijderd schreef op 15 september 2003 @ 21:06:
....
het programma moet zelfstandig orders kunnen inleggen en het is rechtsgeldig omdat ik een koop / verkoop order direct doorstuur naar de internet broker en deze ondersteund dit.

Pas je een beetje op met overflows e.d, zonde van je geld

[RickN]

Verwijderd schreef op 15 september 2003 @ 21:06:
ik heb nog een beetje twijfels over het niet gebruiken van mulit threads, om in plaats daarvan states van aandelen op te slaan. Je krijg dan sequentiele verwerking van data...

Waar ik dan bang voor ben is dat het systeem niet in staat is om meerdere signalen simultaan te verwerken...systeem kan dan te laat reageren op relevante signalen. Dit zal alleen optreden als (worst case scenario) binnen een zeer kort tijdsbestek veel data binnenkomt.

Ook met multithreading (op een singelproc bak) worden instructies nog steeds sequentieel uitgevoerd. Een mogelijk en geldig, maar niet erg waarschijnlijk, trace is dan ook dat alle transacties nog steeds volledig sequenteel worden afgehandeld, net als bij een single treaded oplossing. Je kunt daar niks over zeggen, dat is de verantwoordelijkheid van het OS.

Het is wel veel waarschijnlijker dat er een bepaalde interleaving van de afhandeling van de transacties wordt gescheduled, maar het enige wat dat je oplevert is dat er waarschijnlijk geen wachtrij op je input ontstaat.

Echter, de totale doorlooptijd van de afhandeling van een bepaalde stroom data zal nagenoeg identiek zijn voor single en multithreaded oplossingen, omdat de totale hoeveelheid werk die verzet moet worden niet verandert. Logisch lijkt me.

Dit betekent dus dat als je systeem niet krachtig genoeg is om met een singlethreaded oplossing in real-time op de worstcase datastroom te reageren, dit ook in een multi threaded oplossing niet mogelijk is.

Sterker nog, een singlethreaded oplossing en dus een sequentiele afhandeling van de transacties zal in het algemeen een beter real-time gedrag kunnen garanderen dan een multithreaded oplossing omdat er geen kostbare rekentijd wordt verbruikt voor het afhandelen van een transactie met een latere deadline.

edit:
Bij nader inzien is dit laatste niet helemaal waar. Het hangt een beetje van de context af. Multithreading is denk ik goed om de gemiddelde doorlooptijd van de afhandeling van een transactie omlaag te krijgen, maar die hangt dan wel af van je input rate en is dan dus variable, wat slecht is om realtime eisen te garanderen. Je loopt dan het risico om in een drukke periode ineens geen enkele deadline meer te halen.
Bij een sequentiele afhandeling kun je de deadline van de afhandeling van een transactie en de verwachte duur van zo'n afhandeling gebruiken om selectief transacties te droppen en zo in drukke periodes toch nog zoveel mogelijk transacties op tijd af te handelen.

Daarnaast, wat MSalters al zei, je wilt de rekenintensieve delen van je applicatie niet onderbreken, alleen al vanuit een cache oogpunt.

[ Voor 25% gewijzigd door RickN op 16-09-2003 00:45 ]

[farlane]

Wat me in een multithreaded omgeving ook vervelender lijkt is het synchroniserenvan meerdere transacties van hetzelfde aandeel.
Ik neem aan dat die transacties in de correcte volgorde moeten worden weergegeven? Is voor een groot deel wel afhankelijk van het formaat van de info die je binnenkrijgt. ( Verandering tov de vorige transactie of een absolute waarde )