[PHP] duizenden getallen vergelijken, snelste manier?

[pim]

Ik heb een app gemaakt voor facebook, waarbij je kunt zien na verloop van tijd door wie je ontvriend bent.
Binnen de facebook API krijg ik in een while-lus alle friend-ID's terug:

100000748388181
100000748332463
100000748389266
100000748455336
100000748389266
100000748244145
100000748143439
etc.

Deze lijst sla ik op in mysql.
Nu wil ik bij het volgende bezoek deze lijst vergelijken met de laatste lijst van het vorige bezoek, om te kijken of de twee lijsten hetzelfde zijn.

Momenteel controleer ik nog per ID of het al voorkomt in mysql, maar dat is veeels te zwaar, omdat sommige mensen duizenden vrienden hebben.

Ik zat te denken om alle id's te bufferen, zodat je in extreme gevallen een string krijgt van 45000 tekens lang(15 tekens keer 3000 vrienden); en daar dan een MD5 hash van te maken.
Vervolgens zou ik die Hash kunnen vergelijken met de vorige Hash.

Mijn vraag is eigenlijk meer een bevestiging die ik zoek, is MD5 hier de netste oplossing voor zo'n vergelijking?

[HuHu]

Hoe ziet je query en je tabel eruit?

[ieperlingetje]

met md5 krijg je makkelijk collisions, dus misschien zoek je beter een iets uniekere waarde?

[pim]

Momenteel nog als hieronder, maar dat wil ik helemaal omgooien.

Dit is de tabel:

code:

CREATE TABLE IF NOT EXISTS `facebookfriends` (
  `id` int(20) unsigned NOT NULL auto_increment,
  `uid` bigint(20) unsigned NOT NULL,
  `frienduid` bigint(20) unsigned NOT NULL,
  `first_name` varchar(255) NOT NULL,
  `last_name` varchar(255) NOT NULL,
  `datefriend` date NOT NULL,
  `dateunfriend` date NOT NULL,
  `lastcheck` datetime NOT NULL,
  `friends` int(11) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `uid` (`uid`)
);

Als de App bezocht word, word de vriend-status van alle vrienden op "0" gezet.
Vervolgens krijg ik een Array met alle friend-id's, en stuk voor stuk zet ik de vriend-status weer op "1" als ik het ID kan vinden.

code:

mysql_query('UPDATE facebookfriends SET lastcheck = NOW(), friends = 1 WHERE uid = '.$prints_id.' AND frienduid = '.$uid .' limit 1');

Kan ik het ID niet vinden, dan blijft de vriend-status op 0 staan. Dat zijn automatisch de mensen die geen vrienden meer zijn, en die ik toon als je "Unfriends".

Maar dit te traag dus als deze app gebruikt door veel mensen met veel facebook-vrienden.

[pedorus]

Een hash is een prima methode om te kijken of iets niet is gewijzigd, maar dan moet je evengoed nog nagaan door wie je dan ontvriend bent. Door simpelweg de lijstjes te sorteren (vanuit de DB met order by, en die andere gewoon in php; even de array sorteren) kun je ze vrij makkelijk vergelijken in een loopje.

offtopic:
Verder is dit natuurlijk een sterk 'kijk mij eens vrienden hebben'-topic. Het is dan wel weer jammer dat je blijkbaar alleen maar ontvriend wordt, maar er geen nieuwe bij krijgt. Het lijkt mij dat je als je 0 vrienden over hebt, dat je dan precies weet dat je door allen ontvriend bent. Het simpelst is dus gewoon even wachten tot je er nog maar 0 hebt.

ieperlingetje schreef op vrijdag 12 februari 2010 @ 18:53:
met md5 krijg je makkelijk collisions, dus misschien zoek je beter een iets uniekere waarde?

Dat valt erg mee. Het kan theoretisch, want je kan natuurlijk niet met absolute kans 1 een unieke hash produceren met minder bits dan het origineel. Als dat wel zou kunnen, had je gelijk een zeer goede compressiemethode gehad..

[Cloud]

Het is een beetje afhankelijk van wat je wilt weten. Maar als je wilt weten door wie je ontvriend bent en/of hoeveel je kwijtgeraakt bent lijkt mij hashes vergelijken niet de meest handige manier.

Of bedoel je te zeggen dat je met de hashes van tevoren wilt controleren óf je alle ID's moet gaan vergelijken (omdat je weet dat de hashes verschillen)? Dat kan dan weer wel. Dat zou je cpu tijd kunnen besparen omdat je alleen nog maar vriendenlijsten doorloopt die veranderd zijn.

ieperlingetje schreef op vrijdag 12 februari 2010 @ 18:53:
met md5 krijg je makkelijk collisions, dus misschien zoek je beter een iets uniekere waarde?

Hoe bedoel je 'makkelijk collissions'? En sowieso lijken mij collissions helemaal geen probleem te vormen. Tenminste als ik het idee van de TS goed begrijp. Een collission zou alleen lastig kunnen zijn als de nieuwe hash van één gebruiker zijn vriendenlijst gelijk is aan de hash van zijn oude vriendenlijst.

[pim]

pedorus schreef op vrijdag 12 februari 2010 @ 18:58:
[offtopic]Verder is dit natuurlijk een sterk 'kijk mij eens vrienden hebben'-topic.

Ik denk dat je mijn bericht nog eens goed moet lezen. ik ben niet mijn eigen vrienden aan het vergelijken.
Als het in het huidige temp doorgaat groeit mijn App met +/- 1000 facebookers per maand, dus daarom moet het sneller.

Mijn app http://apps.facebook.com/who-unfriended-me/

[ Voor 22% gewijzigd door pim op 12-02-2010 19:14 ]

[pim]

Cloud schreef op vrijdag 12 februari 2010 @ 18:59:
Of bedoel je te zeggen dat je met de hashes van tevoren wilt controleren óf je alle ID's moet gaan vergelijken (omdat je weet dat de hashes verschillen)? Dat kan dan weer wel. Dat zou je cpu tijd kunnen besparen omdat je alleen nog maar vriendenlijsten doorloopt die veranderd zijn.

Precies! Dat bedoel ik. Als ik van te voren al kan zien dat de lijst onveranderd is, hoef ik ook de controle niet uit te voeren.

[Cloud]

Tja op zich is een MD5 hash dan een makkelijke manier om dat te realiseren. Je zou eventueel ook nog het aantal vrienden bij kunnen houden. Dan kun je de volgende stappen doorlopen:

1. Controleer nieuwe aantal vrienden met oude → is er verschil? Dan lijst doorlopen.
2. Bij geen verschil in aantallen, hashes vergelijken → is er verschil? Dan lijst doorlopen.
3. Geen verschil tussen vriendenlijsten

Zo heb je de meest efficiënte controle het eerst

[Gomez12]

Persoonlijk kies ik in dit soort gevallen meestal voor een tmp-table ( vullen met load data infile ) die vlug gevuld wordt en dan met 4 opeenvolgende query's ( remove equal / new / updated / removed ) werk ik de hoofdtabel bij.

Met grote aantallen werkt dit sneller dan losse waardes... ( Ik heb meer dan 2 miljoen records per keer te verwerken hence the remove equal query die bij weinig updates de 3 volgende query's aanzienlijk versneld )

[RobIII]

Cloud schreef op vrijdag 12 februari 2010 @ 19:14:
Tja op zich is een MD5 hash dan een makkelijke manier om dat te realiseren. Je zou eventueel ook nog het aantal vrienden bij kunnen houden. Dan kun je de volgende stappen doorlopen:

Als alles toch in een grote string geflikkerd wordt, waarom zou je dan nog een hash draaien en niet gewoon die twee strings comparen
Scheelt een hash (die toch door die string moet fietsen én daarbij nog moet rekenen) uitkienen en daarbij introduceer je de kans op collision (hoewel klein).

Zoals ik het begrijp bouwt TS een string van alle ID's die in z'n DB zitten en een string van de ID's die 'ie uit FB krijgt. Nu zou ik niet zo snel naar een string zijn gegaan, maar als 't toch al zo is kun je natuurlijk ook gewoon die strings comparen.

[ Voor 17% gewijzigd door RobIII op 12-02-2010 19:18 ]

[pim]

Probleem is alleen dat je er heel de tijd vrienden bij komen, maar ook afvallen.. Dus het vrienden aantal is niet zo bruikbaar

[pim]

RobIII schreef op vrijdag 12 februari 2010 @ 19:17:
[...]

Als alles toch in een grote string geflikkerd wordt, waarom zou je dan nog een hash draaien en niet gewoon die twee strings comparen

Ja daar zat ik over te twijfelen.. Ik weet niet hoe zwaar het is om een MD5 hash te maken.
Maar mijn mysql database word wel erg groot, als elke member een tekstveld heeft waar een string in kan zitten tot wel 100.000 tekens.

[Brons]

Je hoeft de string toch niet op te slaan in een veld?

[Cloud]

RobIII schreef op vrijdag 12 februari 2010 @ 19:17:
[...]

Als alles toch in een grote string geflikkerd wordt, waarom zou je dan nog een hash draaien en niet gewoon die twee strings comparen

Dan moet hij wel een enorme string (45000 tekens bijv.) opslaan in zijn database, dat lijkt me wel wat veel ruimte kosten i.p.v. een 32-teken hash.

Zoals ik het begrijp bouwt TS een string van alle ID's die in z'n DB zitten en een string van de ID's die 'ie uit FB krijgt. Nu zou ik niet zo snel naar een string zijn gegaan, maar als 't toch al zo is kun je natuurlijk ook gewoon die strings comparen.

Volgens mij is dat dus niet zo, als ik het goed begrijp tenminste. Hij heeft echt een lijst uit FB en een recordset in zijn DB. Als hij echt twee lange strings heeft, is een stringcompare natuurlijk veel beter. Zolang de strings altijd goed gesorteerd zijn natuurlijk.

pim schreef op vrijdag 12 februari 2010 @ 19:17:
Probleem is alleen dat je er heel de tijd vrienden bij komen, maar ook afvallen.. Dus het vrienden aantal is niet zo bruikbaar

Als dat echt zo vaak gebeurt dan scheelt het je toch heel vaak die hash doen? Of zie ik dat nu verkeerd Als de aantallen verschillen, dan weet je toch al zeker dat je de lijst moet gaan lopen vergelijken.

edit:
@ hieronder, daarom dus stap twee in het geval van gelijke aantallen

[ Voor 3% gewijzigd door Cloud op 12-02-2010 19:22 ]

[Caelorum]

ARG. laat maar

[ Voor 93% gewijzigd door Caelorum op 12-02-2010 19:23 ]

[Verwijderd]

Waar je nog niet aan gedacht hebt is het volgende (zie bijv. Wikipedia: diff). Dit kan je dus ook met 2 tekstbestanden doen met diff (dus geen mysql meer gebruiken?!).

1. Maak 2 (identieke) tabellen
2. Bij een update, zet je de nieuwe gegevens in tabel 2
3. Verwijder alle rows in tabel 2 met facebookId voorkomend in tabel 1
4. Uitkomst is een lijst met vrienden die niet meer in de vriendenlijst staan.

Let wel op dat facebook binnenkort zijn privacy zal gaan verbeteren, waardoor je waarschijnlijk niet mere gegevens als voornaam/achternaam zal kunnen zien.

[pim]

Cloud schreef op vrijdag 12 februari 2010 @ 19:21:
Volgens mij is dat dus niet zo, als ik het goed begrijp tenminste. Hij heeft echt een lijst uit FB en een recordset in zijn DB. Als hij echt twee lange strings heeft, is een stringcompare natuurlijk veel beter. Zolang de strings altijd goed gesorteerd zijn natuurlijk.

Juist.

Als dat echt zo vaak gebeurt dan scheelt het je toch heel vaak die hash doen? Of zie ik dat nu verkeerd Als de aantallen verschillen, dan weet je toch al zeker dat je de lijst moet gaan lopen vergelijken.

Ja, maar als ja vandaag 200 vrienden hebt, en morgen 200 vrienden. Kan het zijn dat er een bij is gekomen, en er eentje is afgevallen.

[Cloud]

pim schreef op vrijdag 12 februari 2010 @ 19:24:
[...]

Ja, maar als ja vandaag 200 vrienden hebt, en morgen 200 vrienden. Kan het zijn dat er een bij is gekomen, en er eentje is afgevallen.

Daarvoor was er stap twee in mijn stappenplan; alleen in het geval van gelijke vriendenaantallen ga je hashes vergelijken. Pas als de hashes dan óók gelijk zijn, weet je min of meer zeker dat de vriendenlijst niet veranderd is.

[pim]

Oops, je hebt idd helemaal gelijk!

Ik heb even een testje gedaan met MD5.. Een string omzetten van 100.000.000 tekens, gebeurd in slechts 3 seconden. Dus MD5 is kwa snelheid perfect hiervoor.

[RobIII]

Cloud schreef op vrijdag 12 februari 2010 @ 19:21:
Volgens mij is dat dus niet zo, als ik het goed begrijp tenminste. Hij heeft echt een lijst uit FB en een recordset in zijn DB. Als hij echt twee lange strings heeft, is een stringcompare natuurlijk veel beter. Zolang de strings altijd goed gesorteerd zijn natuurlijk.

Ah, dan begreep ik dat verkeerd.
Ik zou sowieso gewoon al die ID's los op slaan en niet in een text/memo veld gaan zitten frotten. Het is echt niet moeilijk om dan de 'nieuwe lijst' langs de 'bestaande lijst' te houden en een 'diff' uit te rekenen.

Als je 't in code wil doen vul je een dictionary/array/whatever met de ID's uit SQL en die hou je langs de ID's die je van FB krijgt. Nu ben ik geen PHP-er (doe er wel eens wat mee, maar met tegenzin ) maar daar heb je in PHP zelfs functies voor.

In SQL ben je met een temp-tabelletje en een slimme join ook zo klaar.

[ Voor 22% gewijzigd door RobIII op 12-02-2010 19:35 ]

[pedorus]

pim schreef op vrijdag 12 februari 2010 @ 19:06:
[...]

Ik denk dat je mijn bericht nog eens goed moet lezen. ik ben niet mijn eigen vrienden aan het vergelijken.
Als het in het huidige temp doorgaat groeit mijn App met +/- 1000 facebookers per maand, dus daarom moet het sneller.

Mijn app http://apps.facebook.com/who-unfriended-me/

offtopic:
Oh, dus zelf heb je [snip]. Ik denk dat je opmerkingen met een ' 'niet al te serieus moet nemen. Ik zou trouwens even wat antwoorden plaatsen op yahoo answers als je nog meer bezoekers wilt hebben.

Maar goed, mij lijkt me je huidige datamodel op zich ok, lastcheck en friends kunnen enkel weg. lastcheck en de hash gaan dan naar een aparte tabel. Verder is het een kwestie van array_diff en FetchAll() oid gebruiken mocht een hash niet kloppen.

[.oisyn]

Pfff, 3000 id's, waar hebben we het over . Haal ze gewoon allemaal uit de database en vergelijk ze in de applicatie. En idd, gewoon zorgen dat ze gesorteerd zijn (moet je sowieso doen, ook voor de string-vergelijking en de hash-vergelijking), en dan in O(n) tegelijk door de twee lijstjes wandelen op zoek naar de verschillen.

[pasz]

RobIII schreef op vrijdag 12 februari 2010 @ 19:32:
[...]
In SQL ben je met een temp-tabelletje en een slimme join ook zo klaar.

Precies. Helaas wordt SQL vaak misbruikt. Een SQL server is goed in verzamelingen. Dus maak twee verzamelingen en vergelijk deze met elkaar. Laat de loopjes, if..else statements en dat soort crap erbuiten.

[DexterDee]

Als je beide arrays als integers opslaat, dan valt het met het geheugengebruik nog wel mee.
Vervolgens kun je met array_diff() en array_intersect() de verschillen terugkrijgen. Aangezien deze functies als één opcode door PHP uitgevoerd worden, zal het altijd sneller zijn dan je eigen loopje maken en vergelijken.

Alternatief is dat je beide sets in een databasetabel zet en een resultset op basis van JOINs maakt om de verschillen naar boven te halen.

[.oisyn]

DexterDee schreef op vrijdag 12 februari 2010 @ 20:35:
Aangezien deze functies als één opcode door PHP uitgevoerd worden, zal het altijd sneller zijn dan je eigen loopje maken en vergelijken.

Te kort door de bocht, array_intersect() is minstens O(n log n) (en waarschijnlijk O(n²)), aangezien het ook moet werken op ongesorteerde arrays. Voor heel veel elementen kan een stukje PHP code (dat nou ook weer niet zo heel erg ingewikkeld is) best weleens sneller zijn.

[matthijsln]

pim schreef op vrijdag 12 februari 2010 @ 18:46:
Momenteel controleer ik nog per ID of het al voorkomt in mysql, maar dat is veeels te zwaar, omdat sommige mensen duizenden vrienden hebben.

Ik zat te denken om alle id's te bufferen

Dat is een goede gedachte, vooral omdat dat het aantal round-trips (aantal queries) naar mysql beperkt. Nu doe je per friend een query wat erg veel tijd kost. Met de voorgestelde methodes kan je af met 3 queries:

1. een query om de huidige vrienden op te halen:

SQL:

select frienduid from facebookfriends where uid=$uid and friends=1

2. een query om geunfriende friends te updaten:

SQL:

update facebookfriends
set friends=0, dateunfriend=now()
where uid=$uid and frienduid in (<ids van unfriends>)

3. een insert query met meerdere rows voor elke nieuwe friend

zodat je in extreme gevallen een string krijgt van 45000 tekens lang(15 tekens keer 3000 vrienden);

Een bigint is 8 bytes

Voor het bepalen van de lijst met geunfriende ids en nieuwe friends kan je de genoemde merge-join gebruiken, maar je kan ook gewoon simpel hashmaps gebruiken omdat dat misschien wat simpeler is om de lijsten samen te stellen. Omdat dit puur php is zonder roundtrips zal de performance hiervan niet zoveel uitmaken vergeleken met de database queries.

Een hash is trouwens geen oplossing, omdat bij een collision geldt dat je de volledige data moet rechecken. Je weet namelijk alleen indien twee hashes verschillen dat beide inputs gegarandeerd verschillend zijn. Bij een gelijke hash is niet gegarandeerd dat de inputs ook exact gelijk zijn en zul je de beide inputs bit voor bit moeten rechecken. Omdat er heel vaak geen wijzigingen zijn (dus dezelfde hashes en altijd recheck) kan je beter de genoemde oplossingen zonder hash gebruiken.

[Verwijderd]

matthijsln schreef op zaterdag 13 februari 2010 @ 02:19:
Bij een gelijke hash is niet gegarandeerd dat de inputs ook exact gelijk zijn en zul je de beide inputs bit voor bit moeten rechecken.

Onzin. De kans op een collision is zo klein dat je er geen rekening moet houden in een applicatie als deze.

[Soultaker]

.oisyn schreef op vrijdag 12 februari 2010 @ 20:50:
Te kort door de bocht, array_intersect() is minstens O(n log n) (en waarschijnlijk O(n²))

Het is niet minstens O(n log n) want als je alle waarden in een hashtable mikt (wat PHP's array's sowieso gewoon zijn) heb je al O(n) expected time. Dat lijkt me ook dé manier om 't in PHP te implementeren: indien de arrays gelijke lengte hebben, flip je de ene, en itereer je over de waarden van de andere. Kost je n hashtable lookups.

De PHP implementatie sorteert trouwens de inhoud van de arrays eerst en doet daarna een lineaire vergelijking, dus dat is inderdaad O(n log n). (Ik zie dan ook niet waar de "waarschijnlijk O(n²)" vandaan komt )

En idd, gewoon zorgen dat ze gesorteerd zijn (moet je sowieso doen, ook voor de string-vergelijking en de hash-vergelijking)

Is helemaal niet verplicht. Je kunt gewoon iets als Zobrist hashing doen: voor elke vriend afzonderlijk een hashcode berekenen, en die allemaal bij elkaar XOR'en (of optellen of een andere commutatieve operatie). Het resultaat is hetzelfde ongeacht de volgorde van de invoer.

Aangezien het om PHP gaat (waarin je niet handig met bitarrays groter dan een int kan werken) en de arrays niet écht belachelijk groot worden, is sorteren en dan vergelijken geen slechte optie. Dan moet je echter wel beide lijstjes in het geheugen houden, wat voor de hash methode niet nodig was.

[ Voor 15% gewijzigd door Soultaker op 13-02-2010 02:54 ]

[matthijsln]

Verwijderd schreef op zaterdag 13 februari 2010 @ 02:22:
Onzin. De kans op een collision is zo klein dat je er geen rekening moet houden in een applicatie als deze.

Tja, je maakt een correct algoritme of niet...

En wat ruil je ervoor in? Voor het ophalen van de friends zul je misschien wat meer pages uit de storage moeten fetchen. Als je de auto_number kolom dropt en (uid,frienduid) de primary key maakt ordent InnoDB de tabel volgens de primary index en is het ophalen van de friends uit de tabel storage sequentiele reads. Aangezien de app vast regelmatig de unfriended ids voor een bepaalde uid zal tonen is dat zowiezo een goed idee.

stel hash: ~3 random page reads uit index
stel merge: ~3 random page reads uit index + ~10 sequentiele reads + merge-join

Die 10 sequentiele reads en de merge join zijn mij een correct algoritme wel waard lijkt me... Misschien wel leuk om eens te vergelijken.

[Soultaker]

We hebben het wel over een kans van één op 2¹²⁸ voor MD5 (of 2¹⁶⁰ als de TS gelijk SHA-1 of iets dergelijks neemt)! Heb je enig idee hoe klein dat is? Er treedt niet eens een birthday paradox-achtige kansvergroting op, aangezien je alleen vergelijkt met de vorige hash.

En mocht er een hash collision voorkomen, dan is het gevolg dat die Facebook app het gegenereerde lijstje een keer niet refresht. Lekker boeiend.

[ Voor 25% gewijzigd door Soultaker op 13-02-2010 02:56 ]

[matthijsln]

Soultaker schreef op zaterdag 13 februari 2010 @ 02:55:
En mocht er een hash collision voorkomen, dan is het gevolg dat die Facebook app het gegenereerde lijstje een keer niet refresht. Lekker boeiend.

Een catastrophic failure kan je het niet noemen inderdaad

[Wolfboy]

Als je alleen wil weten wie er geunfriend is kan je toch gewoon dit doen?

SQL:

SELECT *
FROM facebookfriends
WHERE uid = [UID]
AND frienduid NOT IN ([friend UIDs])

Daarmee heb je direct alle personen die geen vriend meer zijn, zet er een index op en het is ook nog eens bloedsnel.
NB: mits je query niet te lang wordt (45000 tekens is zeker niet teveel de standaard limiet van mysql staat op 8388608 tekens) is dit zo ongeveer de snelste manier die je kan krijgen.

[ACM]

pim schreef op vrijdag 12 februari 2010 @ 18:57:

code:

mysql_query('UPDATE facebookfriends SET lastcheck = NOW(), friends = 1 WHERE uid = '.$prints_id.' AND frienduid = '.$uid .' limit 1');

Kan ik het ID niet vinden, dan blijft de vriend-status op 0 staan. Dat zijn automatisch de mensen die geen vrienden meer zijn, en die ik toon als je "Unfriends".

Maar dit te traag dus als deze app gebruikt door veel mensen met veel facebook-vrienden.

Hoezo is dat te traag? Die zou vast al een stuk rapper worden als je een unique key op 'uid, frienduid' introduceerde. En er zijn vast handigere oplossingen te verzinnen, maar die vereisen allemaal een compleet andere aanpak dan je nu al hebt.

Als je die unique key hebt op (uid, frienduid), dan kan je ook alle records in een query er in gooien en zowel nieuwe als bestaande records updaten. Dat kan je dan domweg doen door al je records te verzamelen en dan zo'n soort insert bouwen:

SQL:

insert into friends
(uid, frienduid, lastcheck)
values
($ik, 1234, $nu),
($ik, 2345, $nu)
...
ON DUPLICATE KEY UPDATE lastcheck = $nu

Vervolgens maak eventueel ook nog een index op (uid, lastcheck), zodat je de check-query om in 1x te zien wie er allemaal bijgewerkt zijn naar de waarde van $nu wat sneller op kan halen.

[pedorus]

Een unieke index op uid, frienduid lijkt me soweiso een goed idee.

Maar bovenstaande aanpak lijkt me verder niet daadwerkelijk de snelste, aangezien alle betrokken records gelezen en weggeschreven moeten worden, en je redelijk wat onnodige data aan het kopieren bent in het geheugen (onder andere omdat je `first_name`, `last_name` en `datefriend` dan vast ook meestuurt, maar ook bij het aanmaken van de query, parsen, etc.).

Verder leek mij de aanpak van matthijsln wel goed, enkel daar wordt nog geen rekening gehouden met 'gehervrienden'. Verder niet het stukje over hashes natuurlijk, want voordat rekening houden met collissions zinnig is, is rekening houden met foute bits die van de hard disk af komen al een stuk zinniger (wordt soms gedaan, Google doet dit bijvoorbeeld).

[CH4OS]

Wolfboy schreef op zaterdag 13 februari 2010 @ 03:00:
Als je alleen wil weten wie er geunfriend is kan je toch gewoon dit doen?

SQL:

SELECT *
FROM facebookfriends
WHERE uid = [UID]
AND frienduid NOT IN ([friend UIDs])

Daarmee heb je direct alle personen die geen vriend meer zijn, zet er een index op en het is ook nog eens bloedsnel.
NB: mits je query niet te lang wordt (45000 tekens is zeker niet teveel de standaard limiet van mysql staat op 8388608 tekens) is dit zo ongeveer de snelste manier die je kan krijgen.

De tabel / database word echter gevoed vanuit Facebook, lijkt me dat zoiets dus alleen werkt met twee tabellen, anders kan je niet vergelijken.

[Wolfboy]

GJtje schreef op zaterdag 13 februari 2010 @ 14:05:
[...]
De tabel / database word echter gevoed vanuit Facebook, lijkt me dat zoiets dus alleen werkt met twee tabellen, anders kan je niet vergelijken.

Met 2 tabellen zou je een subquery kunnen doen (al is een join dan sowies makkelijker), nu kan je gewoon een comma gescheiden lijst met ID's meegeven om precies hetzelfde te bereiken

[CodeCaster]

Waarom sla je niet iedere keer alle friend-ID's van iemand op, samen met een timestamp? Dus, iemand komt voor het eerst op je app: al de ID's van z'n vrienden worden opgeslagen, in de vorm userID|timestamp|fiendID.

Vervolgens komt diegene nog eens online (dus eigenlijk het geval bij ieder bezoek volgend op het eerste), je slaat de friendID's ook weer in dezelfde tabel op, voorzien van een nieuwe timestamp, en controleert deze met de eerder opgeslagen ID's. De ID's die verschillen (met eerdere timestamp wel aanwezig, maar met latere niet is verwijderd, terwijl bij eerdere timestamp niet aanwezig en in latere wel dan is 'ie toegevoegd) sla je op in een aparte tabel met de nieuwe timestamp en een enum ofzo, A(dded) of D(eleted). Vervolgens kun je alle data van de eerdere timestamp verwijderen.

Zo kun je er prima grafiekjes van tekenen en dergelijke omdat je gewoon netjes per timestamp hebt welke vrienden er bij kwamen of weggingen.

Of denk ik nu te moeilijk?

[ Voor 6% gewijzigd door CodeCaster op 13-02-2010 20:20 ]

[XiniX88]

even snel een idee:

stel je hebt:

code:

100000748388181
100000748332463
100000748389266

dag 1, en

code:

100000748388181
100000748389266  <--- deze verwisseld
100000748332463 <--- met deze

dag 2... andere MD5, zelfde vrienden... wie zegt dat Facebook altijd de ID's in de zelfde volgorde weergeeft?

Denk toch dat het comparen sneller is (zet dit in de index van een array, als het goed is is het een binaire boom, en kan er heel snel vergeleken worden of het getal bestaat of niet. Dus: $myFriends[1231112231] = true;

Edit: Waarom zag ik niet dat er nog een tweede pagina was , ik hoop dat er nu nog nuttige waarde in staat, het gaat mij erom dat MD5 niet ideaal is.

[ Voor 42% gewijzigd door XiniX88 op 14-02-2010 13:20 ]

[.oisyn]

Soultaker schreef op zaterdag 13 februari 2010 @ 02:48:
[...]

Het is niet minstens O(n log n) want als je alle waarden in een hashtable mikt (wat PHP's array's sowieso gewoon zijn) heb je al O(n) expected time. Dat lijkt me ook dé manier om 't in PHP te implementeren: indien de arrays gelijke lengte hebben, flip je de ene, en itereer je over de waarden van de andere. Kost je n hashtable lookups.

Ah ja, de O(n) van hashtables. De lookup is dan wel O(n), maar het inserten niet echt door potentieel dure rehashes. Desalniettemin heb je gelijk dat arrays sowieso hashtables zijn, dus door gewoon lineair te inserten in een lijst werk je dat probleem niet weg. Overigens kan sorten trouwens ook in O(n) met een radix sort

De PHP implementatie sorteert trouwens de inhoud van de arrays eerst en doet daarna een lineaire vergelijking, dus dat is inderdaad O(n log n). (Ik zie dan ook niet waar de "waarschijnlijk O(n²)" vandaan komt )

Dat was gewoon een flauwe opmerking, ik schatte het PHP team dom genoeg om gewoon N keer een in_array te doen

[nescafe]

Kijk naar de oplossing van CodeCaster... CodeCaster in "[PHP] duizenden getallen vergelijken, sn..."

Je slaat sowieso de friend id's op in een tabel om te vergelijken in een volgend bezoek. Het bijhouden van verschillende versies heeft dus geen invloed op de verwerkingstijd, hooguit op de databasegroei. Maar CodeCaster geeft ook aan dat je na het volgende bezoek, je uit de twee versies de verschillen kunt destilleren, deze opslaan en de oudste versie kunt verwijderen.

Voor wat betreft de verschillen zou ik gebruik maken van een (full) outer join in SQL, zo laat je het rekenwerk over aan je db-engine en verdoe je je cpu-tijd in PHP niet aan 'domme' loops.

[Soultaker]

.oisyn schreef op maandag 15 februari 2010 @ 12:33:
Ah ja, de O(n) van hashtables. De lookup is dan wel O(n), maar het inserten niet echt door potentieel dure rehashes.

Klopt. array_flip() heeft echter het voordeel dat 'ie precies weet hoeveel entries het resultaat heeft, dus die kan rehashes waarschijnlijk voorkomen. Dat is onder de aanname dat je de invoer al in arrays hebt natuurlijk.

Dat was gewoon een flauwe opmerking, ik schatte het PHP team dom genoeg om gewoon N keer een in_array te doen

Misschien overschat ik ze nu, maar ik heb het idee dat dingen (redelijk) efficiënt implementeren het enige is dat de PHP developers wél goed kunnen. Het lijkt er op dat hun ontwikkelfilosofie neerkomt op "eerst implementeren, dan pas nadenken", getuige de inconsistente API's, onverklaarbare eigenaardigheden in de taal, eindeloze macro's in de source, chaotische indeling van de CVS repository, et cetera. Dat 't eindproduct geschikt is om op miljoenen webservers in productie te draaien is een klein wonder.

[Wolfboy]

Soultaker schreef op dinsdag 16 februari 2010 @ 19:46:
Misschien overschat ik ze nu, maar ik heb het idee dat dingen (redelijk) efficiënt implementeren het enige is dat de PHP developers wél goed kunnen.

Je bedoelt, ze zijn heel goed in het linken van andere libraries die het efficient kunnen doen?

Dat is ook direct de oorzaak van de inconstistente naamgevingen, ze pakken gewoon de functies uit welke library ze maar even tegenkomen en houden de naamstandaard zoals ie was

[DexterDee]

.oisyn schreef op vrijdag 12 februari 2010 @ 20:50:
[...]

Te kort door de bocht, array_intersect() is minstens O(n log n) (en waarschijnlijk O(n²)), aangezien het ook moet werken op ongesorteerde arrays. Voor heel veel elementen kan een stukje PHP code (dat nou ook weer niet zo heel erg ingewikkeld is) best weleens sneller zijn.

Ik ging er abusievelijk vanuit dat PHP intern de lineaire vergelijking sneller zou uitvoeren dan een handmatige iteratie met behulp van losse PHP statements die door de interpreter los geparsed moeten worden. Omdat ik toch nieuwsgierig ben geworden naar het verschil heb ik maar een benchmark scriptje geschreven:

PHP:

<?php
define('NUMBER_OF_FRIENDS', 3000);
define('MUTATION_MODULO', 30);

$array1 = $array2 = array();
$i = 0;

// vullen van twee arrays met random waarden
// associative om duplicates uit te sluiten
// op de eerste array
while(count($array1)<NUMBER_OF_FRIENDS) {
    $rnd = rand(100000760000000,100000770000000);
    $array1[$rnd] = null;
    if($i % MUTATION_MODULO != 0) {
        $array2[$rnd] = null;
    } else {
        $array2[rand(100000760000000,100000770000000)] = null;
    }
    ++$i;
}

// maak simpele arrays van de associative arrays en sorteer
// $history zijn alle facebook id's van de vorige meting
// $recent zijn alle facebook id's van de huidige meting
$history = array_keys($array1);
$recent = array_keys($array2);
sort($history);
sort($recent);

// initialiseer variabelen voor benchmark
$ir = $ih = 0;
$friends_added = $friends_deleted = array();
$recent_count = count($recent);
$history_count = count($history);

// hier begint de benchmark van methode 1
$start = microtime(true);
while($ir<=$recent_count && $ih<=$history_count) {
    if(!isset($recent[$ir]) && !isset($history[$ih])) {
        break;
    } elseif(!isset($recent[$ir]) && isset($history[$ih])) {
        $friends_deleted[] = $history[$ih];
        ++$ih;
    } elseif(!isset($history[$ih]) && isset($recent[$ir])) {
        $friends_added[] = $recent[$ir];
        ++$ir;
    } elseif($history[$ih] < $recent[$ir]) {
        $friends_deleted[] = $history[$ih];
        ++$ih;
    } elseif($history[$ih] > $recent[$ir]) {
        $friends_added[] = $recent[$ir];
        ++$ir;
    } else {
        ++$ih;
        ++$ir;
    }
}
// bereken totale tijd van methode 1
$duration_method1 = round(microtime(true)-$start,4);

// initialiseer variabelen voor benchmark
$friends_added = $friends_deleted = array();

// hier begint de benchmark van methode 2
$start = microtime(true);
$friends_added = array_diff($recent, $history);
$friends_deleted = array_diff($history, $recent);

// bereken totale tijd van methode 2
$duration_method2 = round(microtime(true)-$start,4);

// meld de uitslag
printf("Methode 1: %01.4f seconden\n",$duration_method1);
printf("Methode 2: %01.4f seconden\n",$duration_method2);

De uitslag is terecht schokkend te noemen. Handmatig itereren over een array van 3000 facebook id's met een mutatie van 100 id's is meer dan 100(!) keer sneller dan de ingebouwde array methode.

Hier de uitslag als ik bovenstaand script in CLI draai op mijn macbookpro:

code:

Methode 1: 0.0015 seconden
Methode 2: 0.1537 seconden

Bij meer mutaties loopt de array_diff methode enorm op, terwijl de handmatige methode veel minder hard omhoog gaat.

De les die hieruit getrokken kan worden is dat het kiezen van het juiste algoritme en complexiteitsfactor een belangrijkere invloed kan hebben op de performance dan het reduceren van PHP opcodes. Je had dus helemaal gelijk .oisyn

[Wolfboy]

DexterDee schreef op dinsdag 16 februari 2010 @ 22:54:
De les die hieruit getrokken kan worden is dat het kiezen van het juiste algoritme en complexiteitsfactor een belangrijkere invloed kan hebben op de performance dan het reduceren van PHP opcodes. Je had dus helemaal gelijk .oisyn

Dan vraag ik me toch af... hoe heeft PHP dit geimplementeerd

[Voutloos]

Omg, dat is wel een aanzienlijk verschil.

Overigens is jouw algoritme bijzonder afhankelijk van de sort() calls en kan de PHP implementatie die aanname niet maken cq. moet ze nog sorteren, dus meet aub eens de tijd van jouw algo incl. voorgaande sorts.

[ Voor 72% gewijzigd door Voutloos op 16-02-2010 23:23 ]

[RobIII]

Wolfboy schreef op dinsdag 16 februari 2010 @ 23:11:
[...]
Dan vraag ik me toch af... hoe heeft PHP dit geimplementeerd

C: php-5.3.1\ext\standard\array.c

static void php_array_diff(INTERNAL_FUNCTION_PARAMETERS, int behavior, int data_compare_type, int key_compare_type) /* {{{ */
{
    zval ***args = NULL;
    HashTable *hash;
    int arr_argc, i, c;
    Bucket ***lists, **list, ***ptrs, *p;
    int req_args;
    char *param_spec;
    zend_fcall_info fci1, fci2;
    zend_fcall_info_cache fci1_cache = empty_fcall_info_cache, fci2_cache = empty_fcall_info_cache;
    zend_fcall_info *fci_key, *fci_data;
    zend_fcall_info_cache *fci_key_cache, *fci_data_cache;
    PHP_ARRAY_CMP_FUNC_VARS;

    int (*diff_key_compare_func)(const void *, const void * TSRMLS_DC);
    int (*diff_data_compare_func)(const void *, const void * TSRMLS_DC);

/* <SNIP> 100+ regels parameter checking verwijderd */

    PHP_ARRAY_CMP_FUNC_BACKUP();

    /* for each argument, create and sort list with pointers to the hash buckets */
    lists = (Bucket ***)safe_emalloc(arr_argc, sizeof(Bucket **), 0);
    ptrs = (Bucket ***)safe_emalloc(arr_argc, sizeof(Bucket **), 0);
    php_set_compare_func(PHP_SORT_STRING TSRMLS_CC);

    if (behavior == DIFF_NORMAL && data_compare_type == DIFF_COMP_DATA_USER) {
        BG(user_compare_fci) = *fci_data;
        BG(user_compare_fci_cache) = *fci_data_cache;
    } else if (behavior & DIFF_ASSOC && key_compare_type == DIFF_COMP_KEY_USER) {
        BG(user_compare_fci) = *fci_key;
        BG(user_compare_fci_cache) = *fci_key_cache;
    }

    for (i = 0; i < arr_argc; i++) {
        if (Z_TYPE_PP(args[i]) != IS_ARRAY) {
            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
            arr_argc = i; /* only free up to i - 1 */
            goto out;
        }
        hash = Z_ARRVAL_PP(args[i]);
        list = (Bucket **) pemalloc((hash->nNumOfElements + 1) * sizeof(Bucket *), hash->persistent);
        if (!list) {
            PHP_ARRAY_CMP_FUNC_RESTORE();

            efree(ptrs);
            efree(lists);
            efree(args);
            RETURN_FALSE;
        }
        lists[i] = list;
        ptrs[i] = list;
        for (p = hash->pListHead; p; p = p->pListNext) {
            *list++ = p;
        }
        *list = NULL;
        if (behavior == DIFF_NORMAL) {
            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *), diff_data_compare_func TSRMLS_CC);
        } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *), diff_key_compare_func TSRMLS_CC);
        }
    }

    /* copy the argument array */
    RETVAL_ZVAL(*args[0], 1, 0);
    if (return_value->value.ht == &EG(symbol_table)) {
        HashTable *ht;
        zval *tmp;

        ALLOC_HASHTABLE(ht);
        zend_hash_init(ht, zend_hash_num_elements(return_value->value.ht), NULL, ZVAL_PTR_DTOR, 0);
        zend_hash_copy(ht, return_value->value.ht, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
        return_value->value.ht = ht;
    }

    /* go through the lists and look for values of ptr[0] that are not in the others */
    while (*ptrs[0]) {
        if ((behavior & DIFF_ASSOC) /* triggered also when DIFF_KEY */
            &&
            key_compare_type == DIFF_COMP_KEY_USER
        ) {
            BG(user_compare_fci) = *fci_key;
            BG(user_compare_fci_cache) = *fci_key_cache;
        }
        c = 1;
        for (i = 1; i < arr_argc; i++) {
            Bucket **ptr = ptrs[i];
            if (behavior == DIFF_NORMAL) {
                while (*ptr && (0 < (c = diff_data_compare_func(ptrs[0], ptr TSRMLS_CC)))) {
                    ptr++;
                }
            } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
                while (*ptr && (0 != (c = diff_key_compare_func(ptrs[0], ptr TSRMLS_CC)))) {
                    ptr++;
                }
            }
            if (!c) {
                if (behavior == DIFF_NORMAL) {
                    if (*ptrs[i]) {
                        ptrs[i]++;
                    }
                    break;
                } else if (behavior == DIFF_ASSOC) {  /* only when DIFF_ASSOC */
                    /* In this branch is execute only when DIFF_ASSOC. If behavior == DIFF_KEY
                     * data comparison is not needed - skipped. */
                    if (*ptr) {
                        if (data_compare_type == DIFF_COMP_DATA_USER) {
                            BG(user_compare_fci) = *fci_data;
                            BG(user_compare_fci_cache) = *fci_data_cache;
                        }
                        if (diff_data_compare_func(ptrs[0], ptr TSRMLS_CC) != 0) {
                            /* the data is not the same */
                            c = -1;
                            if (key_compare_type == DIFF_COMP_KEY_USER) {
                                BG(user_compare_fci) = *fci_key;
                                BG(user_compare_fci_cache) = *fci_key_cache;
                            }
                        } else {
                            break;
                            /* we have found the element in other arrays thus we don't want it
                             * in the return_value -> delete from there */
                        }
                    }
                } else if (behavior == DIFF_KEY) { /* only when DIFF_KEY */
                    /* the behavior here differs from INTERSECT_KEY in php_intersect
                     * since in the "diff" case we have to remove the entry from
                     * return_value while when doing intersection the entry must not
                     * be deleted. */
                    break; /* remove the key */
                }
            }
        }
        if (!c) {
            /* ptrs[0] in one of the other arguments */
            /* delete all entries with value as ptrs[0] */
            for (;;) {
                p = *ptrs[0];
                if (p->nKeyLength == 0) {
                    zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
                } else {
                    zend_hash_quick_del(Z_ARRVAL_P(return_value), p->arKey, p->nKeyLength, p->h);
                }
                if (!*++ptrs[0]) {
                    goto out;
                }
                if (behavior == DIFF_NORMAL) {
                    if (diff_data_compare_func(ptrs[0] - 1, ptrs[0] TSRMLS_CC)) {
                        break;
                    }
                } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
                    /* in this case no array_key_compare is needed */
                    break;
                }
            }
        } else {
            /* ptrs[0] in none of the other arguments */
            /* skip all entries with value as ptrs[0] */
            for (;;) {
                if (!*++ptrs[0]) {
                    goto out;
                }
                if (behavior == DIFF_NORMAL) {
                    if (diff_data_compare_func(ptrs[0] - 1, ptrs[0] TSRMLS_CC)) {
                        break;
                    }
                } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
                    /* in this case no array_key_compare is needed */
                    break;
                }
            }
        }
    }
out:
    for (i = 0; i < arr_argc; i++) {
        hash = Z_ARRVAL_PP(args[i]);
        pefree(lists[i], hash->persistent);
    }

    PHP_ARRAY_CMP_FUNC_RESTORE();

    efree(ptrs);
    efree(lists);
    efree(args);
}

[ Voor 20% gewijzigd door RobIII op 16-02-2010 23:32 ]

[Wolfboy]

Omg.... per item in array 1 controleren of ie in 1 van de andere arrays zit... WTF

.oisyn schreef op vrijdag 12 februari 2010 @ 20:50:
[...]

Te kort door de bocht, array_intersect() is minstens O(n log n) (en waarschijnlijk O(n²)), aangezien het ook moet werken op ongesorteerde arrays. Voor heel veel elementen kan een stukje PHP code (dat nou ook weer niet zo heel erg ingewikkeld is) best weleens sneller zijn.

Je had nog gelijk ook... O(n*m)

[ Voor 73% gewijzigd door Wolfboy op 16-02-2010 23:30 ]

[.oisyn]

DexterDee schreef op dinsdag 16 februari 2010 @ 22:54:
Je had dus helemaal gelijk .oisyn

Zeg dat nog 'ns

Overigens, wat je nu niet meemeet is de sort(). Nu zijn de items in de database vrijwel automatisch gesort, maar de array die binnenkomt van facebook moet je wellicht alsnog sorten. Met de array_diff() methode hoeft dat niet, dus het is wel zo eerlijk om de tijd van de sort bij methode1 op te tellen.

Ook zou ik wel willen weten hoe Soultakers voorstel performt (met een array_flip())

[pedorus]

De vergelijking lijkt mij niet heel eerlijk, omdat die uitging van een 64 bit systeem, en waarschijnlijk deze bug. Als ik vergelijk:

PHP:

define('NUMBER_OF_FRIENDS', 3000);
define('MUTATION_MODULO', 30);
function array_diff_2($array1, $array2, &$result2) {
    $array1 = array_flip($array1);
    $result2 = array();

    foreach($array2 as $val) {
       if (isset($array1[$val]))
           unset($array1[$val]);
       else
           $result2[] = $val;
    }

    return array_keys($array1);
}

$array1 = $array2 = array();
$i = 0;
while(count($array1)<NUMBER_OF_FRIENDS) {
    $rnd = '100000' . rand(760000000,770000000);
    $array1[$rnd] = 1;
    if($i % MUTATION_MODULO != 0) {
        $array2[$rnd] = 1;
    } else {
        $array2['100000' . rand(760000000,770000000)] = 1;
    }
    ++$i;
}

$history = array_keys($array1);
$recent = array_keys($array2);
sort($history);
$start = microtime(true);
sort($recent);
$duration_sort = microtime(true)-$start;

$start = microtime(true);
$ir = $ih = 0;
$friends_added = $friends_deleted = array();
while(true) {
    $r = $recent[$ir];
    $h = $history[$ih];
    if(!isset($h)) {
       if (!isset($r)) break;
       $friends_added[] = $r;
       ++$ir;
    } elseif((!isset($r)) || ($h < $r)) {
        $friends_deleted[] = $h;
        ++$ih;
    } elseif($h > $r) {
        $friends_added[] = $r;
        ++$ir;
    } else {
        ++$ih;
        ++$ir;
    }
}
$duration_method1 = microtime(true)-$start;

$start = microtime(true);
$friends_added2 = array_diff($recent, $history);
$friends_deleted2 = array_diff($history, $recent);
$duration_method2 = microtime(true)-$start;

$start = microtime(true);
$friends_added3 = array_diff_2($recent, $history, $friends_deleted3);
$duration_method3 = microtime(true)-$start;

printf("Sorteren:  %01.4f seconden\n",$duration_sort);
printf("Methode 1: %01.4f seconden\n",$duration_method1);
printf("Methode 2: %01.4f seconden\n",$duration_method2);
printf("Methode 3: %01.4f seconden\n",$duration_method3);

Sorteren:  0.0533 seconden
Methode 1: 0.0154 seconden
Methode 2: 0.0301 seconden
Methode 3: 0.0154 seconden 

Oftewel, array_diff_2 (array_flip) werkt het beste.

[ACM]

Wolfboy schreef op dinsdag 16 februari 2010 @ 23:27:
Omg.... per item in array 1 controleren of ie in 1 van de andere arrays zit... WTF

Ik moet zeggen dat ik na een paar minuten turen nog niet zo zeker ben dat het wel O(n*m*...) is, er worden allerlei pointers naar de (gesorteerde) buckets opgehoogd op diverse plekken. Eigenlijk een beetje wat de code van DexterDee ook lijkt te doen. Maar het kan natuurlijk ook mijn gebrekkige c-kennis zijn, waardoor ik gewoon niet goed herken dat ie af en toe een pointer weer op de beginplek krijgt.

array_diff heeft iig als nadeel dat ze in principe een oneindige lijst met arrays kunnen krijgen om tegen te vergelijken, de while-loop van DexterDee is dan ineens een stuk complexer als je een variant voor 3, 4, 5 etc array's zou moeten maken
Bovendien heeft het als nadeel dat de array_diff 2x gedaan wordt, en je dus 2x het hele sorteergebeuren krijgt, zelfs als ze de meest efficiente variant hebben genomen.

De array_diff_2-implementatie werkt overigens niet zo best als de values wat anders zijn dan strings of ints, in dit geval werkt dat uiteraard prima, maar dat is ook een shortcut die men bij array_diff niet kan nemen.

[DexterDee]

pedorus schreef op woensdag 17 februari 2010 @ 01:02:
De vergelijking lijkt mij niet heel eerlijk, omdat die uitging van een 64 bit systeem, en waarschijnlijk deze bug. Als ik vergelijk:

Sorteren:  0.0533 seconden
Methode 1: 0.0154 seconden
Methode 2: 0.0301 seconden
Methode 3: 0.0154 seconden 

Oftewel, array_diff_2 (array_flip) werkt het beste.

Wat betreft die bug ziet het er naar uit dat je gelijk hebt. De slechte score van de array_diff lijkt inderdaad te maken te hebben met die bug.

Ik ben inderdaad bewust uitgegaan van een 64 bit PHP versie bij het opbouwen van de associative keys. Ik heb ergens gelezen dat PHP er intern toch string hashes van maakt omdat de getallen niet opeenlopend zijn, dus voor de performance zou het bitter weinig uitmaken. De notatie is alleen iets simpeler.

Jouw script gooit wel wat notices op:

code:

PHP Notice:  Undefined offset:  3000 in fb2.php on line 42
PHP Stack trace:
PHP   1. {main}() fb2.php:0
PHP Notice:  Undefined offset:  3000 in fb2.php on line 43
PHP Stack trace:
PHP   1. {main}() fb2.php:0

De vertraging van twee notices is verwaarloosbaar, maar het is netjes om deze te voorkomen.

Bij 3000 id's en 100 mutaties is de performance van de handmatige iteratie en de alternatieve array_diff vrijwel gelijk (afgezien van de verplichte sort):

Sorteren:                0.0010 seconden
Handmatige Iteratie:     0.0015 seconden
Array_diff:              0.1568 seconden
Alternatieve array_diff: 0.0015 seconden

Bij 30.000 id's en 1000 mutaties loopt het verschil al een beetje op tussen de twee methodieken, waarbij de handmatige iteratie de helft sneller is:

Sorteren:                0.0169 seconden
Handmatige Iteratie:     0.0200 seconden
Array_diff:              11.7558 seconden
Alternatieve array_diff: 0.0312 seconden

Bij 300.000 id's en 10.000 mutaties is de handmatige iteratie bijna 2 keer zo snel:

Sorteren:                0.4770 seconden
Handmatige Iteratie:     0.2451 seconden
Array_diff:              1141.6529 seconden
Alternatieve array_diff: 0.4659 seconden

De conclusie is dus dat wanneer je van facebook géén gesorteerde array van id's terug krijgt, de alternatieve array_diff altijd sneller is dan de handmatige iteratie. Geeft facebook echter wél een gesorteerde array terug, dan is het sneller om handmatig te itereren, vooral bij grotere datasets.

Die bug is trouwens wel vervelend, zoals je hierboven kan zien heb ik 19 minuten moeten wachten op de array_diff benchmark. Je zal deze functie maar gebruiken en upgraden naar een nieuwere PHP versie

Dan rest mij nog één vraag. Als ik jouw getallen vergelijk met die van mij met gelijke parameters, dan is de performance op mijn machine grofweg het tienvoudige van die van jou. Dat vind ik een enorm verschil. Ik vraag me af waar dat aan ligt. Onder welke omstandigheden heb je deze test gedraaid?

Ik draai deze tests op een MacBookPro 17" model 2009, OSX Snow Leopard, PHP 5.3.0 64-bit

Ik weet dat ze met PHP 5.3 naar de performance hebben gekeken, maar dan nog vind ik het een erg groot verschil.

[Soultaker]

Uit die testen hierboven lijkt de conclusie me vooral dat alles goed is, als je maar niet array_diff() gebruikt. Slecht natuurlijk, want de het is veel helderder om een standaardfunctie te schrijven dan om 'm zelf te herimplementeren. (Wel fijn om bevestigd te zien dat de array_flip() methode compact en efficiënt is.)

Trouwens, weet iemand waarom als ik aan pedorus' code dit toevoeg:

code:

echo ($friends_added    == $friends_added2) ? "ok\n" : "faal\n";
echo ($friends_added2   == $friends_added3) ? "ok\n" : "faal\n";
echo ($friends_deleted  == $friends_deleted2) ? "ok\n" : "faal\n";
echo ($friends_deleted2 == $friends_deleted3) ? "ok\n" : "faal\n";

print_r(array_diff($friends_added,  $friends_added2));
print_r(array_diff($friends_added2, $friends_added3));
print_r(array_diff($friends_deleted,  $friends_deleted2));
print_r(array_diff($friends_deleted2, $friends_deleted3));

De uitvoer vier keer "faal" is, maar er daarna wel vier lege arrays geprint worden? Volgens de PHP docs zijn arrays gelijk als ze dezelfde key/value pairs hebben. Waarom is dat hier niet zo? (Bij voorbaat excuses voor de topickaping.)

[DexterDee]

Soultaker schreef op woensdag 17 februari 2010 @ 12:33:

Trouwens, weet iemand waarom als ik aan pedorus' code dit toevoeg:

code:

echo ($friends_added    == $friends_added2) ? "ok\n" : "faal\n";
echo ($friends_added2   == $friends_added3) ? "ok\n" : "faal\n";
echo ($friends_deleted  == $friends_deleted2) ? "ok\n" : "faal\n";
echo ($friends_deleted2 == $friends_deleted3) ? "ok\n" : "faal\n";

print_r(array_diff($friends_added,  $friends_added2));
print_r(array_diff($friends_added2, $friends_added3));
print_r(array_diff($friends_deleted,  $friends_deleted2));
print_r(array_diff($friends_deleted2, $friends_deleted3));

De uitvoer vier keer "faal" is, maar er daarna wel vier lege arrays geprint worden? Volgens de PHP docs zijn arrays gelijk als ze dezelfde key/value pairs hebben. Waarom is dat hier niet zo? (Bij voorbaat excuses voor de topickaping.)

Dat komt omdat de handmatige iteratie oplopende numeric keys maakt en de alternatieve array_diff keys unset waardoor de resulterende array niet meer keurig opeenvolgende numeric keys heeft. De == compare kijkt of de twee arrays exact hetzelfde zijn en geeft false terug omdat dit dus niet zo is op basis van de numeric key index.

[pedorus]

DexterDee schreef op woensdag 17 februari 2010 @ 11:17:
Dan rest mij nog één vraag. Als ik jouw getallen vergelijk met die van mij met gelijke parameters, dan is de performance op mijn machine grofweg het tienvoudige van die van jou. Dat vind ik een enorm verschil. Ik vraag me af waar dat aan ligt. Onder welke omstandigheden heb je deze test gedraaid?

Ik draai deze tests op een MacBookPro 17" model 2009, OSX Snow Leopard, PHP 5.3.0 64-bit

Dat zal komen doordat ik dit op een wat oudere unix 32 bit webserver met php 5.2 heb getest (exacte specificaties zo niet bij de hand). Ik had ook nog even SORT_STRING getest, toen kwam er 0.0077s uit, dus dat was ook al een factor 7 sneller. En dit is natuurlijk een geval waar 64 bit echt een enorm voordeel is, ook omdat php geen long's kent. Hier op een linux amd64 (helaas: exacte processor onbekend) php 5.3.1 32 bit:

Sorteren:  0.0153 seconden
Methode 1: 0.0036 seconden
Methode 2: 0.0535 seconden
Methode 3: 0.0033 seconden 

Dat komt al iets meer in de buurt. Sorteren gaat nog steeds erg langzaam, met SORT_STRING is dit 0.0043.

Overigens zorgt 2x een '@' toevoegen tegen die notices voor een tijdsverdubbeling, en ook met een extra test kost het duidelijk iets aan performance. Dus daar zit een tradeoff tussen netjes programmeren en snelheid.

Soultaker schreef op woensdag 17 februari 2010 @ 12:33:
De uitvoer vier keer "faal" is, maar er daarna wel vier lege arrays geprint worden? Volgens de PHP docs zijn arrays gelijk als ze dezelfde key/value pairs hebben. Waarom is dat hier niet zo? (Bij voorbaat excuses voor de topickaping.)

Voeg ook even dit toe dan:

PHP:

sort($friends_added2);
sort($friends_deleted2);

[Soultaker]

@DexterDee: Ah, je hebt gelijk! En array_diff() vergelijkt natuurlijk alleen waarden, geen keys. Ik had met var_dump() moeten kijken naar die arrays, niet met print_r(), dan had ik 't zelf gezien.

pedorus schreef op woensdag 17 februari 2010 @ 12:42:
Voeg ook even dit toe dan:

PHP:

sort($friends_added2);
sort($friends_deleted2);

Wilden we sorteren niet juist voorkomen? (Niet dat dat veel uitmaakt ten opzichte van de huidige performance van array_diff() maar OK.) Of is sort() extra snel op gesorteerde arrays? Anders moet er toch een betere manier zijn om alleen de keys te relabelen maar de waarden te behouden, lijkt me, maar het beste wat ik zo snel op php.net kon vinden was array_merge($array, array())...

[ Voor 61% gewijzigd door Soultaker op 17-02-2010 12:46 ]

[DexterDee]

Soultaker schreef op woensdag 17 februari 2010 @ 12:43:
@DexterDee: Ah, je hebt gelijk! En array_diff() vergelijkt natuurlijk alleen waarden, geen keys. Ik had met var_dump() moeten kijken naar die arrays, niet met print_r(), dan had ik 't zelf gezien.

De suggestie van Pedorus werkt ook (eerst de arrays door sort heenhalen), maar dat heeft als reden dat sort() de numeric keys re-ordered, waardoor er weer een opvolgende base-0 key index ontstaat

[ACM]

Soultaker schreef op woensdag 17 februari 2010 @ 12:43:
Anders moet er toch een betere manier zijn om alleen de keys te relabelen maar de waarden te behouden, lijkt me, maar het beste wat ik zo snel op php.net kon vinden was array_merge($array, array())...

Wellicht wil je dan gewoon array_values() hebben?

[ Voor 19% gewijzigd door ACM op 17-02-2010 12:51 ]

[pedorus]

Je kan ook het volgende doen, maar dat was meer typwerk:

PHP:

$friends_added2=array_values($friends_added2);
$friends_deleted2=array_values($friends_deleted2);

sort lijkt trouwens wel iets sneller bij gesorteerde waardes, maar performance leek me bij dit stukje toch niet zo interessant.

[Soultaker]

ACM schreef op woensdag 17 februari 2010 @ 12:50:
Wellicht wil je dan gewoon array_values() hebben?

Ja, dat lijkt me de goede functie eigenlijk.

Wel raar dat er geen in-place functie voor is.

[ Voor 51% gewijzigd door Soultaker op 17-02-2010 12:52 ]

[DexterDee]

Ik denk overigens dat deze testjes voor de TS wel wat verheldering geven over een mogelijke oplossingsrichting.

Op een beetje snelle server kun je met een gemiddelde dataset van 3000 facebook id's met 100 mutaties toch al dik 500 gebruikers per seconde berekenen (exclusief database en andere overhead natuurlijk). Dat lijkt me snel genoeg voor een succesvolle implementatie

[Wolfboy]

ACM schreef op woensdag 17 februari 2010 @ 08:16:
Ik moet zeggen dat ik na een paar minuten turen nog niet zo zeker ben dat het wel O(n*m*...) is, er worden allerlei pointers naar de (gesorteerde) buckets opgehoogd op diverse plekken. Eigenlijk een beetje wat de code van DexterDee ook lijkt te doen. Maar het kan natuurlijk ook mijn gebrekkige c-kennis zijn, waardoor ik gewoon niet goed herken dat ie af en toe een pointer weer op de beginplek krijgt.

Dit maakt het helaas toch al direct een O(n*(m+...)) implementatie. Niet O(n*m*...) inderdaad

C:

    /* go through the lists and look for values of ptr[0] that are not in the others */ 
    while (*ptrs[0]) { 
        /* snip */
        c = 1; 
        for (i = 1; i < arr_argc; i++) { 
            Bucket **ptr = ptrs[i]; 
            if (behavior == DIFF_NORMAL) { 
                while (*ptr && (0 < (c = diff_data_compare_func(ptrs[0], ptr TSRMLS_CC)))) { 
                    ptr++; 
                } 
            } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */ 
                while (*ptr && (0 != (c = diff_key_compare_func(ptrs[0], ptr TSRMLS_CC)))) { 
                    ptr++; 
                } 
            }

array_diff heeft iig als nadeel dat ze in principe een oneindige lijst met arrays kunnen krijgen om tegen te vergelijken, de while-loop van DexterDee is dan ineens een stuk complexer als je een variant voor 3, 4, 5 etc array's zou moeten maken
Bovendien heeft het als nadeel dat de array_diff 2x gedaan wordt, en je dus 2x het hele sorteergebeuren krijgt, zelfs als ze de meest efficiente variant hebben genomen.

De array_diff_2-implementatie werkt overigens niet zo best als de values wat anders zijn dan strings of ints, in dit geval werkt dat uiteraard prima, maar dat is ook een shortcut die men bij array_diff niet kan nemen.

Dat is zeker waar, al zou een implementatie voor meerdere arrays ook weer niet zo heel erg spannend zijn. Plak ze allemaal aan elkaar, sorteer ze en opeens heb je ook een array_diff voor 2 arrays.

Loop dan door alle items heen, doe een gok waar je items zitten (als de ene array een range van 0-50 is en de andere van 25-75 dan kan je natuurlijk proberen direct wat verder naar voren te springen).

Hoe dan ook, efficienter dan dit moet het zeker kunnen.

[pedorus]

Wolfboy schreef op woensdag 17 februari 2010 @ 13:27:
Dit maakt het helaas toch al direct een O(n*(m+...)) implementatie. Niet O(n*m*...) inderdaad

Nee, want die pointers van de lijstjes waarin gezocht wordt gaan alleen maar omhoog, en starten niet steeds opnieuw. Het algoritme is dat ze eerst de lijstjes sorteren (die zend_qsort), en dan afgaan (hoewel er dus ergens een performance-bug zit). Heel erg vergelijkbaar met 'methode 1' dus, en dus ongeveer nlogn+mlogm+... voor het sorteren, en m+n+... voor het checken.

[Voutloos]

ACM schreef op woensdag 17 februari 2010 @ 08:16:
[...]

Ik moet zeggen dat ik na een paar minuten turen nog niet zo zeker ben dat het wel O(n*m*...) is, er worden allerlei pointers naar de (gesorteerde) buckets opgehoogd op diverse plekken. Eigenlijk een beetje wat de code van DexterDee ook lijkt te doen. Maar het kan natuurlijk ook mijn gebrekkige c-kennis zijn, waardoor ik gewoon niet goed herken dat ie af en toe een pointer weer op de beginplek krijgt.

+

pedorus schreef op woensdag 17 februari 2010 @ 18:21:
[...]
Nee, want die pointers van de lijstjes waarin gezocht wordt gaan alleen maar omhoog, en starten niet steeds opnieuw.

Op regel 87 van RobIII in "[PHP] duizenden getallen vergelijken, sn..." wordt de pointer van de huidige array welke bekeken wordt gereset. Die loop gaat dus over alle arrays (muv de refentie array) en begint elke keer van voren af aan.

Voor zover ik het begrijp zal er veel tijd in het comparen en pointer opgehogen (regels 88-96) zitten. Dat is ongelooflijk stupide, maar zit er blijkbaar om een probleem met een bepaalde behavior/data_compare_type te voorkomen.

Wellicht kan het sneller (en imo leesbaarder) als ze deze functie uit elkaar trekken in meerdere functies met een specifieker algoritme afhankelijk van de gekozen behavior.

edit:

Of gewoon enkel 'if (behavior & DIFF_ASSOC)' de ptr resetten als enkel die behavior voor bug 42838 zorgde. Bijna te simpel en effectief...

[ Voor 21% gewijzigd door Voutloos op 17-02-2010 21:55 ]

[Bolukan]

Sorteren gaat nog steeds erg langzaam, met SORT_STRING is dit 0.0043.

In die tijd knipper jij niet met je ogen...

[Wolfboy]

pedorus schreef op woensdag 17 februari 2010 @ 18:21:
[...]

Nee, want die pointers van de lijstjes waarin gezocht wordt gaan alleen maar omhoog, en starten niet steeds opnieuw. Het algoritme is dat ze eerst de lijstjes sorteren (die zend_qsort), en dan afgaan (hoewel er dus ergens een performance-bug zit). Heel erg vergelijkbaar met 'methode 1' dus, en dus ongeveer nlogn+mlogm+... voor het sorteren, en m+n+... voor het checken.

Je hebt gelijk idd, ik las over het feit dat "Bucket **ptr = ptrs[i]" een referentie is in plaats van een kopie heen.

[Voutloos]

Bolukan schreef op woensdag 17 februari 2010 @ 23:25:
[...]


In die tijd knipper jij niet met je ogen...

Leuk die :X, maar het gaat om een enkel function call he. Je hoeft niet eens zo heel vaak 4ms te verspillen in je script voordat mensen zeggen dat je een trage *(&@^$site hebt hoor.

Wolfboy schreef op woensdag 17 februari 2010 @ 23:45:
[...]
Je hebt gelijk idd, ik las over het feit dat "Bucket **ptr = ptrs[i]" een referentie is in plaats van een kopie heen.

Toch wordt de waarde van ptrs[i] nooit verhoogd.

[ Voor 59% gewijzigd door Voutloos op 17-02-2010 23:49 ]

[Soultaker]

Wel als behavior == DIFF_NORMAL en de waarde in de eerste array is gevonden in één van de volgende arrays. Waarom ze dat überhaupt nog doen is me een raadsel. Lijkt me eerder een nieuwe bug dan een feature met deze implementatie.

[pedorus]

Voutloos schreef op woensdag 17 februari 2010 @ 23:46:
Toch wordt de waarde van ptrs[i] nooit verhoogd.

Verdomd, ik heb een oudere 5.2-versie bekeken die andere code had die dit niet deed. Ik had verwacht dat ptrs[i] dan later wel werd geupdate - niet dus. De versie die ik heb bekeken was van voor deze patch, gelinkt vanaf dat bugreport: diff.

Wel een vrij gekke patch zeg, het is natuurlijk precies die performancebug... Aan de andere kant is het ook wel lekkere spaghetticode natuurlijk, waardoor je dat kan krijgen. Ik kan me zelfs voorstellen dat diegene nog dacht de performance te verhogen. Op zich is het heel makkelijk weer te fixen.

[Soultaker]

Ik lees trouwens de documentatie van array_diff en array_diff_assoc en daar staat:

Two values from key => value pairs are considered equal only if (string) $elem1 === (string) $elem2. In other words a strict check takes place so the string representations must be the same.

Waarom zou je dan niet gewoon het equivalent doen van:

PHP:

function array_diff($a, &$b) {
    $have = array();
    foreach ($b as $val) {
        $have[(string)$val] = TRUE;
    }
    foreach ($a as $key => $val) {
        if (array_key_exists((string)$val, !$have)) {
            unset($a[$key]);
        }
    }
    return $a;
}

(Uitbreiden naar meerdere arrays is triviaal.) Heb je wel een hoop conversies naar string, maar het zal allicht efficiënter zijn dan wat ze nu hebben, en een stuk beter onderhoudbaar. Desnoods maak je een aparte $have arrays voor ints en strings; dan kun je je in het waarschijnlijke geval dat de invoer uit ints of strings bestaat veel conversies besparen.

Ik dacht dat het oorspronkelijke probleem juist voortvloeide uit het feit dat mogelijke waarden niet totaal geordend zijn (waardoor sorteren en lineair vergelijken niet werkt) maar als je alles toch naar strings converteert voor het vergelijken zie ik niet hoe dit probleem optreedt.

[ Voor 26% gewijzigd door Soultaker op 18-02-2010 00:39 ]

[DexterDee]

Ter leering ende vermaeck heb ik de benchmark vandaag eens door de facebook hiphop compiler gehaald om te zien of hier nog enige performance winst te halen viel. We hebben het tenslotte over Facebook id's

Op de server met de hiphop binaries, scoort 'vanilla' PHP als volgt:

Sorteren:                0.0012 seconden
Handmatige Iteratie:     0.0017 seconden
Array_diff:              0.1423 seconden
Alternatieve array_diff: 0.0012 seconden

Als ik de sourcecode door hiphop haal, maakt hiphop er C++ van en compiled een native 64bit binary voor me. Bij het uitvoeren van deze binary krijg ik deze resultaten:

Sorteren:                0.0137 seconden
Handmatige Iteratie:     0.0036 seconden
Array_diff:              0.1564 seconden
Alternatieve array_diff: 0.0025 seconden

Ik had eerlijk gezegd wel iets meer verwacht hiervan. Niet alleen is het behoorlijk wat langzamer, maar ook de array_diff bug hebben ze blijkbaar geport. De binary is ook behoorlijk groot te noemen, 29 megabyte!

Voor de geïnteresseerden, de C++ code die hiphop genereert op basis van de PHP code:

C:

#include <php/fb.h>
#include <cpp/ext/ext.h>

namespace HPHP {
///////////////////////////////////////////////////////////////////////////////

const int64 k_MUTATION_MODULO = 30LL;
const int64 k_NUMBER_OF_FRIENDS = 3000LL;

/* preface starts */
/* preface finishes */
/* SRC: fb.php line 7 */
Variant f_array_diff_2(Variant v_array1, CVarRef v_array2, Variant v_result2) {
  FUNCTION_INJECTION(array_diff_2);
  DECLARE_GLOBAL_VARIABLES(g);
  Variant v_val;

  (v_array1 = LINE(8,x_array_flip(v_array1)));
  (v_result2 = ScalarArrays::sa_[0]);
  {
    LOOP_COUNTER(1);
    for (ArrayIterPtr iter3 = v_array2.begin(); !iter3->end(); iter3->next()) {
      LOOP_COUNTER_CHECK(1);
      v_val = iter3->second();
      {
        if (isset(v_array1, v_val)) v_array1.weakRemove(v_val);
        else v_result2.append((v_val));
      }
    }
  }
  return LINE(18,x_array_keys(v_array1));
} /* function */
Variant pm_php$fb_php(bool incOnce /* = false */, LVariableTable* variables /* = NULL */) {
  FUNCTION_INJECTION(run_init::fb.php);
  {
    DECLARE_GLOBAL_VARIABLES(g);
    bool &alreadyRun = g->run_pm_php$fb_php;
    if (alreadyRun) { if (incOnce) return true;}
    else alreadyRun = true;
    if (!variables) variables = g;
  }
  DECLARE_GLOBAL_VARIABLES(g);
  LVariableTable *gVariables __attribute__((__unused__)) = get_variable_table();
  Variant &v_array2 __attribute__((__unused__)) = (variables != gVariables) ? variables->get("array2") : g->GV(array2);
  Variant &v_array1 __attribute__((__unused__)) = (variables != gVariables) ? variables->get("array1") : g->GV(array1);
  Variant &v_i __attribute__((__unused__)) = (variables != gVariables) ? variables->get("i") : g->GV(i);
  Variant &v_rnd __attribute__((__unused__)) = (variables != gVariables) ? variables->get("rnd") : g->GV(rnd);
  Variant &v_history __attribute__((__unused__)) = (variables != gVariables) ? variables->get("history") : g->GV(history);
  Variant &v_recent __attribute__((__unused__)) = (variables != gVariables) ? variables->get("recent") : g->GV(recent);
  Variant &v_start __attribute__((__unused__)) = (variables != gVariables) ? variables->get("start") : g->GV(start);
  Variant &v_duration_sort __attribute__((__unused__)) = (variables != gVariables) ? variables->get("duration_sort") : g->GV(duration_sort);
  Variant &v_ih __attribute__((__unused__)) = (variables != gVariables) ? variables->get("ih") : g->GV(ih);
  Variant &v_ir __attribute__((__unused__)) = (variables != gVariables) ? variables->get("ir") : g->GV(ir);
  Variant &v_friends_deleted __attribute__((__unused__)) = (variables != gVariables) ? variables->get("friends_deleted") : g->GV(friends_deleted);
  Variant &v_friends_added __attribute__((__unused__)) = (variables != gVariables) ? variables->get("friends_added") : g->GV(friends_added);
  Variant &v_recent_count __attribute__((__unused__)) = (variables != gVariables) ? variables->get("recent_count") : g->GV(recent_count);
  Variant &v_history_count __attribute__((__unused__)) = (variables != gVariables) ? variables->get("history_count") : g->GV(history_count);
  Variant &v_duration_method1 __attribute__((__unused__)) = (variables != gVariables) ? variables->get("duration_method1") : g->GV(duration_method1);
  Variant &v_duration_method2 __attribute__((__unused__)) = (variables != gVariables) ? variables->get("duration_method2") : g->GV(duration_method2);
  Variant &v_duration_method3 __attribute__((__unused__)) = (variables != gVariables) ? variables->get("duration_method3") : g->GV(duration_method3);

  LINE(2,x_ini_set("memory_limit", "256M"));
  ;
  ;
  (v_array1 = (v_array2 = ScalarArrays::sa_[0]));
  (v_i = 0LL);
  LOOP_COUNTER(4);
  {
    while (less(LINE(27,x_count(v_array1)), 3000LL /* NUMBER_OF_FRIENDS */)) {
      LOOP_COUNTER_CHECK(4);
      {
        (v_rnd = toInt64(LINE(28,x_rand(100000760000000LL, 100000770000000LL))));
        v_array1.set(v_rnd, (null));
        if (!equal(modulo(toInt64(v_i), 30LL /* MUTATION_MODULO */), 0LL)) {
          v_array2.set(v_rnd, (null));
        }
        else {
          v_array2.set(toInt64(LINE(33,x_rand(100000760000000LL, 100000770000000LL))), (null));
        }
        ++v_i;
      }
    }
  }
  (v_history = LINE(41,x_array_keys(v_array1)));
  (v_recent = LINE(42,x_array_keys(v_array2)));
  LINE(43,x_sort(ref(v_history)));
  (v_start = LINE(44,x_microtime(true)));
  LINE(45,x_sort(ref(v_recent)));
  (v_duration_sort = LINE(46,x_microtime(true)) - v_start);
  (v_ir = (v_ih = 0LL));
  (v_friends_added = (v_friends_deleted = ScalarArrays::sa_[0]));
  (v_recent_count = LINE(51,x_count(v_recent)));
  (v_history_count = LINE(52,x_count(v_history)));
  (v_start = LINE(55,x_microtime(true)));
  LOOP_COUNTER(5);
  {
    while (not_more(v_ir, v_recent_count) && not_more(v_ih, v_history_count)) {
      LOOP_COUNTER_CHECK(5);
      {
        if (!(isset(v_recent, v_ir)) && !(isset(v_history, v_ih))) {
          break;
        }
        else if (!(isset(v_recent, v_ir)) && isset(v_history, v_ih)) {
          v_friends_deleted.append((v_history.rvalAt(v_ih)));
          ++v_ih;
        }
        else if (!(isset(v_history, v_ih)) && isset(v_recent, v_ir)) {
          v_friends_added.append((v_recent.rvalAt(v_ir)));
          ++v_ir;
        }
        else if (less(v_history.rvalAt(v_ih), v_recent.rvalAt(v_ir))) {
          v_friends_deleted.append((v_history.rvalAt(v_ih)));
          ++v_ih;
        }
        else if (more(v_history.rvalAt(v_ih), v_recent.rvalAt(v_ir))) {
          v_friends_added.append((v_recent.rvalAt(v_ir)));
          ++v_ir;
        }
        else {
          ++v_ih;
          ++v_ir;
        }
      }
    }
  }
  (v_duration_method1 = LINE(77,x_microtime(true)) - v_start);
  (v_friends_added = (v_friends_deleted = ScalarArrays::sa_[0]));
  (v_start = LINE(83,x_microtime(true)));
  (v_friends_added = LINE(84,x_array_diff(2, v_recent, v_history)));
  (v_friends_deleted = LINE(85,x_array_diff(2, v_history, v_recent)));
  (v_duration_method2 = LINE(88,x_microtime(true)) - v_start);
  (v_friends_added = (v_friends_deleted = ScalarArrays::sa_[0]));
  (v_start = LINE(94,x_microtime(true)));
  (v_friends_added = LINE(95,f_array_diff_2(v_recent, v_history, ref(v_friends_deleted))));
  (v_duration_method3 = LINE(96,x_microtime(true)) - v_start);
  LINE(99,x_printf(2, "Sorteren:                %01.4f seconden\n", Array(ArrayInit(1).set(0, v_duration_sort).create())));
  LINE(100,x_printf(2, "Handmatige Iteratie:     %01.4f seconden\n", Array(ArrayInit(1).set(0, v_duration_method1).create())));
  LINE(101,x_printf(2, "Array_diff:              %01.4f seconden\n", Array(ArrayInit(1).set(0, v_duration_method2).create())));
  LINE(102,x_printf(2, "Alternatieve array_diff: %01.4f seconden\n", Array(ArrayInit(1).set(0, v_duration_method3).create())));
  return true;
} /* function */

///////////////////////////////////////////////////////////////////////////////
}

Enig lichtpuntje van die big-ass executable is dat er ook een ingebouwde webserver in gecompileerd is. Door de executable met de parameters -m server op te starten ontstaat een webserver die de code kan displayen in de browser.

Facebook zei al dat hiphop-php niet voor iedereen ging zijn. En zoals dit eruit ziet hebben ze daar volkomen gelijk in Hopelijk doet een (grote) website het performance-wise iets beter.

[Soultaker]

Ik vermoed dat ze de C modules van PHP gewoon verbatim overgenomen hebben (dus ook array_diff() e.d.) en alleen de PHP code transformeren naar C++. Vandaar dat er hier weinig winst te behalen valt, want er wordt nauwelijks PHP code uitgevoerd: de meeste tijd zit 'm in het uitvoeren van hashtable insertions en dat soort dingen, die in de oorspronkelijke PHP interpreter ook al in C geïmplementeerd waren.

Het is wel verdacht dat functies zoals array_sort() en array_diff() waarvan ik dus denk dat ze hetzelfde geïmplementeerd zijn, trager zijn geworden. Heb je wel dezelfde optimalisaties e.d. gebruikt?

Ook wel typisch trouwens dat de handmatige array_diff() trager geworden is, want dat is één van de weinige methoden die nogal zwaar leunde op in PHP geschreven code. Als er ergens winst te behalen zou zijn, zou je verwachten dat het dáár was.

[ Voor 16% gewijzigd door Soultaker op 22-02-2010 22:14 ]

[DexterDee]

Soultaker schreef op maandag 22 februari 2010 @ 22:13:
Het is wel verdacht dat functies zoals array_sort() en array_diff() waarvan ik dus denk dat ze hetzelfde geïmplementeerd zijn, trager zijn geworden. Heb je wel dezelfde optimalisaties e.d. gebruikt?

Met hiphop heb je geen invloed op compiler opties of andere optimalisatie truuks. Het porten, compilen en linken wordt allemaal integraal en achter elkaar gedaan door de hphp commandline tool. Het is m.i. juist de bedoeling dat je de PHP code er ongewijzigd doorheen haalt en daar performance winst uit haalt zonder te prutsen en te sleutelen. Anders kun je evengoed je huidige code refactoren met het oog op performance.

De array_sort() is dusdanig langzamer geworden dat ik niet snap wat daar gebeurd is. Met een beetje moeite is de C++ code achter deze functie wel te achterhalen om erachter te komen wat hiervan de oorzaak is.