[PHP] class constant trager dan setter

[xces]

Het idee van dit topic is om even wat kennis te delen. Zelf ben ik bezig om mijn code wat te optimaliseren en loop zo tegen een aantal dingen aan. Het achterliggende idee is om een stelling neer te zetten waarvan jij denkt dat het sneller/beter is en waarom. Vervolgens kun je dit testen door onderstaand testscript te gebruiken. Het testscript is natuurlijk slechts een template, en zou veel mooier gemaakt kunnen worden, maar het is ook maar een snel in elkaar gezet ding.

Maar goed; de aftrap.

Stelling: (PHP5) Class constants zijn sneller dan de waarde in de klasse via een setter instellen.
Resultaat: Fout. Het is sneller om een variabele te hebben en deze in de constructor in te stellen, dan gebruik te maken van class constants.
Tijd: Testcase één: 4 seconden / Testcase twee: 6 seconden.

PHP:

<?php
    error_reporting(E_ALL ^ E_NOTICE ^ E_WARNING);
    setlocale(LC_ALL, nl_NL);

    /**
     * Test class
     */
    class wuTest {
        private $strTest;

        /**
         * Constructor
         * @param object
         */
        public function __construct() {
            $this->setTest(65536);
        }

        public function setTest($strValue) {
            $this->strTest = $strValue;
        }

        public function getTest() {
            return $this->strTest;
        }
    }

    /**
     * Test class
     */
    class wuTest2 {
        const TEST = 65536;

        public function getTest() {
            return TEST;
        }
    }

    //
    // Test code
    $intStart = microtime(true);
    for ($intCurrent=0; $intCurrent<500000; $intCurrent++) {
        $objTest = new wuTest();
        $objTest->getTest();
        unset($objTest);
    }
    echo 'Test 1: '.sprintf("%01.4f", (microtime(true) - $intStart)).'<br />';

    $intStart = microtime(true);
    for ($intCurrent=0; $intCurrent<500000; $intCurrent++) {
        $objTest = new wuTest2();
        $objTest->getTest();
        unset($objTest);
    }
    echo 'Test 2: '.sprintf("%01.4f", (microtime(true) - $intStart));
?>

Het zou misschien leuk zijn om hier een "performance" topic van te maken. Dus niet direct vragen stellen, maar meer van "doe niet dit, maar dit is beter". Zo kunnen we leren van elkaar..

[RAJH]

PHP:

$intStart = microtime(true);
for ($intCurrent=0; $intCurrent<500000; $intCurrent++) {
    wuTest2::TEST;
}
echo 'Test 3: '.sprintf("%01.4f", (microtime(true) - $intStart)).'<br />';

Test 1: 13.2510
Test 2: 7.6963
Test 3: 0.9099

Het static aanroepen van een constante is aanzienlijk sneller

[Kalentum]

Niet eens met de stelling:

code:

Test 1: 2.0629<br />Test 2: 1.7899
Test 1: 2.0068<br />Test 2: 1.7489
Test 1: 2.0075<br />Test 2: 1.7855
Test 1: 2.0400<br />Test 2: 1.7627
Test 1: 1.9950<br />Test 2: 1.7787

PHP 5.2.0

[xces]

Vaag dat het bij jullie wel sneller is (ik draai overigens wel op Windhoos Windows nu, maar dat is ivm werk redenen). Ik zal het straks eens testen op een Linux server.

Waar ik constants voor wil gebruiken is bij inheritance, dan werkt jouw oplossing niet (static aanroepen).

Casus: Stel dat je nl één generieke db klasse hebt. (test1) en daarvan erf je een klasse die met 1 specifiek tabel werkt (test2). In test2 zet je de naam van de tabel, de PK etc. Dit define je als constants. Wat ik hiermee wil bereiken is dat ik in de base klasse (test1) alle conversie, insert en update statements kan doen.

Oplossing:

PHP:

    /**
     * Test class
     */
    class wuTest1 {
        public function getTest() {
            return $this->TEXT_MAX;
        }
    }

    /**
     * Test class
     */
    class wuTest2 extends wuTest1 {
        const TEXT_MAX = 65536;
    }

[Janoz]

De keuze tussen een constante en een property is een keuze die je absoluut niet moet maken op basis van een paar microseconden, maar op basis van hoe je domein er uit ziet.

[xces]

@Janoz; De reden dat ik hier nu over nadenk, is dat ik een denkfout heb gemaakt in een groot stuk van mijn code. Ik had een redelijk generiek klasse die gebruik maakte van call_user_func / call_user_array en van __call / __get / __set methoden.

Hiermee heb ik uiteindelijk een MPTT klasse gebouwd welke 100% werkt. het generen van een complete tree (met 4200 files) duurt echter veel ste lang (145 seconden op een server die niks doet) en wat snelle tests hebben uitgewezen dat de gebruikte functies van overloaden een dermate performance impact hebben dat het nuttig is om een deel opnieuw te schrijven. Overigens heeft dit niets te maken met de MPTT implementatie, want de tree is iedere keer weer kloppend, en ook move/swap/delete en add methodes gaan zoals ze horen te gaan.

Mgoed; Stel dat 1 klasse 20 velden heeft, en het over al die 20 velden slechts 2 milliseconden scheelt. Doe dat maal 4000 en dan heb je toch al weer 8 secondes gewonnen. Als je dan toch opnieuw begint, kun je meteen dit erbij pakken toch?

[ Voor 9% gewijzigd door xces op 09-05-2008 11:07 ]

[Woy]

xces schreef op vrijdag 09 mei 2008 @ 10:58:
Vaag dat het bij jullie wel sneller is (ik draai overigens wel op Windhoos nu, maar dat is ivm werk redenen). Ik zal het straks eens testen op een Linux server.

Waar ik constants voor wil gebruiken is bij inheritance, dan werkt jouw oplossing niet (static aanroepen).

Casus: Stel dat je nl één generieke db klasse hebt. (test1) en daarvan erf je een klasse die met 1 specifiek tabel werkt (test2). In test2 zet je de naam van de tabel, de PK etc. Dit define je als constants. Wat ik hiermee wil bereiken is dat ik in de base klasse (test1) alle conversie, insert en update statements kan doen.

Oplossing:

PHP:

    /**
     * Test class
     */
    class wuTest1 {
        public function getTest() {
            return $this->TEXT_MAX;
        }
    }

    /**
     * Test class
     */
    class wuTest2 extends wuTest1 {
        const TEXT_MAX = 65536;
    }

Sorry hoor maar wuTest1 hoort in deze situatie imho helemaal niet de constant van wuTest2 terug te geven. IMHO hoort een constant gewoon hetzelfde gedrag te vertonen als een static readonly field. Die kan je dus alleen op het type waar hij in is gedefineerd oproepen.

wuTest1 kan op deze manier toch zowiezo niet werken?

[eamelink]

xces schreef op vrijdag 09 mei 2008 @ 10:31:
Dus niet direct vragen stellen, maar meer van "doe niet dit, maar dit is beter". Zo kunnen we leren van elkaar..

Doe dit niet!

In dit soort nano-optimalisaties is geen winst te behalen, tenzij je een extreme low-level library aan het maken bent en als dat het geval is kan je beter een php module schrijven dan het in php zelf doen

Verder betwijfel ik sterk of je nu echt meet wat je wilt meten. Je doet een vage stelling over dingen die sneller 'zijn'. Een ding kan niet snel zijn, een actie kan snel zijn. Een class constant is niet iets waar een snelheid aan verbonden zit. Hooguit aan het schrijven of het lezen ervan. Je testcase daarentegen is waarschijnlijk vooral bezig met een half miljoen keer een object constructen en destructen

Ik maak gebruik van xdebug om php scripts te profilen, dat geeft een heel aardig overzicht van de bottlenecks en helpt om de juiste dingen te optimaliseren

[xces]

rwb schreef op vrijdag 09 mei 2008 @ 11:07:
[...]
Sorry hoor maar wuTest1 hoort in deze situatie imho helemaal niet de constant van wuTest2 terug te geven. IMHO hoort een constant gewoon hetzelfde gedrag te vertonen als een static readonly field. Die kan je dus alleen op het type waar hij in is gedefineerd oproepen.

wuTest1 kan op deze manier toch zowiezo niet werken?

True, de achterliggende denkwijze is om een generiek basis object te bouwen waar een hoop werk in zit (zoals conversies van datums/tijden tussen PHP/SQL etc.) zodat dit niet meer in de klasses zelf hoeft te zitten en ik dus ook minder fouten kan maken.

@eamelink: Aangezien alle testcases dezelfde constructor/destructor gebruiken is dat toch te verwaarlozen?

[ Voor 7% gewijzigd door xces op 09-05-2008 11:12 ]

[Confusion]

xces schreef op vrijdag 09 mei 2008 @ 11:06:
Hiermee heb ik uiteindelijk een MPTT klasse gebouwd welke 100% werkt. het generen van een complete tree (met 4200 files) duurt echter veel ste lang (145 seconden op een server die niks doet) en [..]

Dat ga je niet fixen door op 500000 calls een winst van 2 seconden te halen.

[xces]

@rwb: zoiets bedoel ik dus (pseudo en dus vol fouten):

PHP:

<?php
    /**
     * Test class
     */
    class wuTest1 {
        protected $strTable = '';
        protected $strPkField = '';

        public function __construct(&$objDb) {
            //
            // Zeker weten dat de database verbonden is
            $this->objDb = $objDb;
            if (!$this->objDb->isConnected()) {
                // .. exception
            }
        }

        protected function queryAll() {
            // select $this->strPkField from $this->strTable ...
        }
    }

    /**
     * Test class
     */
    class wuTest2 extends wuTest1 {
        /**
         * Constructor
         * @param object
         */
        public function __construct(&$objDb) {
            $this->strTable = 'test';
            $this->strPKField = 'testid';

            return $this->queryAll();
        }
    }
?>

@De rest: jullie hebben gelijk, maar als dit simpele testgeval op mijn systeem toch al zo veel verschil had, dan snap je toch dat ik het ff kwijt was en schrok van de verschillen?

[Janoz]

xces schreef op vrijdag 09 mei 2008 @ 11:06:
Mgoed; Stel dat 1 klasse 20 velden heeft, en het over al die 20 velden slechts 2 milliseconden scheelt. Doe dat maal 4000 en dan heb je toch al weer 8 secondes gewonnen. Als je dan toch opnieuw begint, kun je meteen dit erbij pakken toch?

Mijn punt is juist dat een constante conceptueel verschilt van een property. De keuze tussen een constante of een property is daarom ook niet afhankelijk van de snelheid, maar of iets een constante of juist een property zou moeten zijn.

Dat je performance problemen hebt kun je beter oplossen door te kijken of je je algoritmen en datastructuren kunt verbeteren en eventueel wat caching toe kunt voegen. Je domein 'verkrachten' door properties om te zetten naar constanten lijkt me niet een juiste weg.

Wat ik me eventueel nog wel voor zou kunnen stellen is dat je nu bepaalde conviguratie variabelen hebt die je als property gebruikt omdat deze ergens uit een configuratie bestand gelezen worden. Deze zou je kunnen vervangen door zelf een soort van compileer slag uit te voeren waarbij je je php code genereert en dus alle constanten in die stap invult.

[xces]

@Janoz; en dat is dus wat ik wil bereiken bij mijn voorgaande post;

Misschien kan ik mijn vraag dan beter zo stellen:
Performance daargelaten; is het beter om bijv. strPkField en strTable als een constante in "test2" te stellen en aan te roepen vanuit Test1, of is het slimmer om ze in test1 te initializeren op blank en ze vanuit test2 te vullen in de constructor? (en ze dus als variabelen te gaan gebruiken ipv constanten).

[Confusion]

xces schreef op vrijdag 09 mei 2008 @ 11:17:
@De rest: jullie hebben gelijk, maar als dit simpele testgeval op mijn systeem toch al zo veel verschil had, dan snap je toch dat ik het ff kwijt was en schrok van de verschillen?

Nee, dat snap ik niet. Zelfs als het waar zou zijn, zou het niet erg relevant zijn voor veruit de meeste taken, inclusief de jouwe.

[Voutloos]

xces schreef op vrijdag 09 mei 2008 @ 11:17:
jullie hebben gelijk, maar als dit simpele testgeval op mijn systeem toch al zo veel verschil had

Foute statistiek. Alles staat in een context. Het testen van een micro optimalisatie terwijl in je script een inefficient algoritme staat is echt compleet weggegooide tijd.

Ik durf te stellen dat jij absoluut niet weet wat de bottleneck van je programma is. Optimaliseren begint met profilen, tenzij de bottleneck je op een presenteerblaadje gemeld wordt (bijv. db slow query log).

Heel veel optimalisatie topics en blogpostings verliezen de context totaal uit het oog. Ook in de PHP optimalisatie topics op GoT (zijn er menig geweest) is meer dan 50% van de posts compleet k*t omdat er enkel over micro optimalisaties gewauweld wordt. Als jouw topicopzet slaagt en mensen stellingen gaan plaatsen, verwacht ik meer stellingen over micro optimalisaties dan boeiende optimalisaties. Klinkt pessimistisch, maar het topic is alvast met de 1e micro optimalisatie begonnen.

[Confusion]

Voutloos schreef op vrijdag 09 mei 2008 @ 11:36:
[...]
Als jouw topicopzet slaagt en mensen stellingen gaan plaatsen, verwacht ik meer stellingen over micro optimalisaties dan boeiende optimalisaties.

Volgens mij is dat onvermijdelijk, omdat de boeiende optimalisaties vaak nogal probleem specifiek zijn. Tenzij we naar de triviale categorie overstappen. Dan wil ik wel een stelling lanceren: als je een grote lijst met items hebt en je moet vaak zoeken of een bepaald item bestaat: gooi de items dan in een HashMap/Dictionary/ander hashcode gebaseerde structuur. Zoeken of een element bestaat in een lijst kost je (mits je niet domweg ieder element gaat vergelijken) O(log(n)) tijd; zoeken in een HashMap kost O(1) (constante) tijd. Is dat het soort bedoelde optimalisaties?

edit:
Aangepast naar aanleiding van onderstaande uitleg; hier stond eerst "[..] O(n) tijd; zoeken in een HashMap kost O(log(n)) [..]"

[ Voor 12% gewijzigd door Confusion op 12-05-2008 16:07 ]

[Voutloos]

Dat is imo al een betere soort. Een datastructuur welke beter op het gebruik aansluit heeft gewoon meer impact dan een paar keer een dubbele quote door een enkele te vervangen, om maar een klassieker erbij te halen. En de verbetering kunnen uitleggen dmv big O() notation scoort natuurlijk ook.

En ja, het wordt al gauw probleem specifiek. Maar jij weet er nu ook een te omschrijven zonder te zeggen waarvoor die lijst nodig is en het zoeken in lijstjes is wel een veel voorkomende taak. Maar in opsomtopics scoren oneliners welke je uit oneindig vaak gekopieerde 'top 10 PHP Performance tips' kan halen nou eenmaal beter.

Ik zie hier liever dus de mogelijkheid om na te denken of bepaalde algoritmes en datastructuren van de ts beter kunnen.

[Woy]

xces schreef op vrijdag 09 mei 2008 @ 11:20:
is het beter om bijv. strPkField en strTable als een constante in "test2" te stellen en aan te roepen vanuit Test1, of is het slimmer om ze in test1 te initializeren op blank en ze vanuit test2 te vullen in de constructor?

Dat is het punt wat ik wilde maken, vanuit Test1 hoor je constanten uit Test2 niet aan te roepen. Je moet constanten alleen gebruiken als je al weet uit welk type het komt. Bij inheritance is dit niet het geval.

Ik zou gewoon een getTable en getPkField methode defineren in een abstracte class/interface en die dan implementeren in de sub-class. In je sub-class kun je het dan eventueel implementeren met een constante.

Een beetje als het volgende

code:

abstract class DbSuperClass
{
    function GetTable();
    function GetPkField();

    function DoSomethingGeneric()
    {
          //Hier GetTable en GetPkField gebruiken
    }
}

class DbImpClass : DbSuperClass
{
     const TABLE = "MyTable";
     const PK_FIELD = "MyPkField";

     function GetTable()
    {
         return TABLE;
    }

    fuction GetPkField()
    {
        return PK_FIELD;
    }
}

[ Voor 24% gewijzigd door Woy op 09-05-2008 12:15 ]

[xces]

Als ik een dergelijke klasse gebouwd heb, hebben jullie dan interesse om er eens kritisch naar te kijkeN?

[PrisonerOfPain]

Confusion schreef op vrijdag 09 mei 2008 @ 11:47:
zoeken in een HashMap kost O (log(n)) tijd.

Search en insertion in een hashmap zijn over het algemeen O(1), tenzij er collisions zijn (dan is het meestal O(m) voor het aantal items in die bucket). Verder kan de performance van de hash functie op den duur ook parten spelen deze te complex is.

[Confusion]

PrisonerOfPain schreef op zondag 11 mei 2008 @ 20:25:
Search [..] in een hashmap zijn over het algemeen O(1),

Doe mij die zoekmethode die in constante tijd het gezochte element tussen een willekeurige hoeveelheid elementen vindt?

[.oisyn]

Euhm, een hashtable is in theorie gewoon O(1) hoor. Net als een array, waarbij je zegt dat je het Nde element wil hebben. Dan is je key gelijk aan de index. In een hashtable is niet N je index in de array, maar juist hash(key). Bij een goede uniforme hash functie en een table die groot genoeg is is een lookup daardoor O(1).

[ Voor 3% gewijzigd door .oisyn op 12-05-2008 04:07 ]

[ACM]

xces schreef op vrijdag 09 mei 2008 @ 11:06:
Hiermee heb ik uiteindelijk een MPTT klasse gebouwd welke 100% werkt. het generen van een complete tree (met 4200 files) duurt echter veel ste lang (145 seconden op een server die niks doet) en wat snelle tests hebben uitgewezen dat de gebruikte functies van overloaden een dermate performance impact hebben dat het nuttig is om een deel opnieuw te schrijven.

Wordt dus tijd om - bijvoorbeeld - xdebug te installeren op je server of testomgeving en te profilen welke functies zoveel tijd kosten. Let er op dat je dat niet met je productieomgeving doet, want xdebug vertraagd de boel sowieso een beetje (uiteraard als je gaat profilen nog veel meer).
De resultaten kun je vervolgens prima met kcachegrind op linux of wincachegrind op windows bekijken.

Bedenk overigens wel dat bij profilen functies die relatief weinig tijd kosten eventueel te zwaar afgeschilderd kunnen worden. Dat geld voor PHP overigens niet zo sterk als bijvoorbeeld voor Java, maar een optimalisatie die in je geprofilede versie flink uitmaakt kan betrekkelijk zinloos blijken als je geen profiler meer draait.

Ik denk dat het voor je php-code zeker ook belangrijk is dat je niet continu nieuwe objecten aan het maken bent en dat je kijkt naar de hoeveelheid geheugen die je objecten gebruiken. Zelf viel mij de overhead van het gebruik van duizenden objecten in php vies tegen, je gebruikt al gauw enkele kilobytes geheugen per object! En meer geheugen gebruiken zal bijna per definitie vertraging opleveren. Verder zou ik kijken of je af kan stappen van de __call/__set/__get-functies, als je al probeert te microoptimaliseren lijkt dat me juist de eerste stap om te nemen. Maar ik geloof dat je dat al aan het doen bent?

[ACM]

Voutloos schreef op vrijdag 09 mei 2008 @ 11:57:
Een datastructuur welke beter op het gebruik aansluit heeft gewoon meer impact

Helaas kent PHP zelf geen andere datastructuren dan de multifunctionele array/hashmap/queue/list.

dan een paar keer een dubbele quote door een enkele te vervangen, om maar een klassieker erbij te halen. En de verbetering kunnen uitleggen dmv big O() notation scoort natuurlijk ook.

Dat ben ik met je eens en toch ook weer niet. In mijn ervaring bleken bepaalde zaken die ik eerder afgedaan zou hebben als microoptimalisatie behoorlijk wat impact te hebben. Met name kijkend naar geheugengebruik en de daarbij behorende performance. Als je veel objecten van een bepaald type gebruikt en een deel van de properties is maar in beperkt aantal gevallen nodig, dan loont het al snel om die maar heel vies niet te definieren in de class-definitie en gewoon maar ongedefinieerd te setten als blijkt dat ze nodig zijn... De overhead om een referentie naar de propertie te houden is namelijk nogal fors, iig ruim meer dan de paar bytes die het bijvoorbeeld in C of Java kost.

Voor arrays geldt iets vergelijkbaars, voor een bepaald algoritme heb ik op een gegeven moment maar delen van een grote tweedimensionele sparse matrix met floats en integer-keys (iets waar php's hashgebeuren in het voordeel zou moeten zijn) uiteindelijk maar geserialized omdat dat veel minder geheugen gebruikte dan de sub-arrays zelf in het geheugen te houden... En dan hebben het over verschillen van '512MB ram is veel te weinig' vs 'met 512MB houden we nog aardig wat geheugen over'. Ik geloof dat ik had uitgerekend dat de getallen zelf met gemak binnen een paar MB hadden moeten passen.

[ Voor 5% gewijzigd door ACM op 12-05-2008 09:10 ]

[xces]

ACM schreef op maandag 12 mei 2008 @ 08:28:
[...]

Ik denk dat het voor je php-code zeker ook belangrijk is dat je niet continu nieuwe objecten aan het maken bent en dat je kijkt naar de hoeveelheid geheugen die je objecten gebruiken. Zelf viel mij de overhead van het gebruik van duizenden objecten in php vies tegen, je gebruikt al gauw enkele kilobytes geheugen per object! En meer geheugen gebruiken zal bijna per definitie vertraging opleveren.

Correct. Ik zal je vertellen; sinds mijn servers over zijn gegaan van PHP4 naar PHP5 ben ik eigenlijk alles gaan ombouwen naar objecten. Alles, alsin: Veel van mijn sites gebruiken basecode die ik in de laatste jaren heb "verzameld" en geoptimaliseerd. Zo heb ik een validatieklasse, date time parsing functies wrapper om phpmailer heen die automatisch images attached, enzovoorts. De nieuwe sites, krijgen dan meteen een opfriscursus voor de achterliggende code

De MPTT klasse had (schrik niet) 63 meg geheugen nodig, om een tree met 4000 entrys te initializeren (grofweg 20 folders en de rest files). OO-gezien heb ik het goed aangepakt, met recursie bedoel ik. Maar aan de andere kant heb ik het ook weer fout gedaan; Zoals je misschien weet werkt MPTT met "left" en "right" waardes. Ook al voegde ik vanuit het object weer nieuwe childnodes toe, wijzigde ik de waardes van de parent niet, dus het parent object was zoiezo geen reeele weergave van de huidige staat in de database.

4000 objecten in het geheugen bijhouden is ook helemaal niet interessant, want ik deed er toch niets mee. Ook het weergeven van deze objecten doe ik nu altijd zo (pseudo):

code:

list($arrData, $intCount) = $object->loadChildren(<van>, <tot>, <extra_where>, <extra_order>);

Vervolgens assignde ik het object aan de template, wat als voordeel oplevert dat je het object in zijn geheel in de template kunt gebruiken. Aan de andere kant is dat natuurlijk juist iets wat je wilt vermijden, aangezien de template voor DISPLAY gebruikt moet worden en eigenlijk niets anders moet doen dan kant en klare data aanleveren.

Moraal van het verhaal; ik "dacht" dat OO in PHP dé oplossing was, maar dit blijkt bij dit soort scenario's dus weer niet het geval;

hoe gebruiken jullie objecten in PHP dan?
Een verbeterslag zou kunnen zijn dat ik geen objecten maar slechts een array met DIE waardes die ik ook nodig heb meegeef aan het script. Dit scheelt natuurlijk geheugen, maar dan stap je weer van objecten af..

ACM schreef op maandag 12 mei 2008 @ 08:28:
[...]
Verder zou ik kijken of je af kan stappen van de __call/__set/__get-functies, als je al probeert te microoptimaliseren lijkt dat me juist de eerste stap om te nemen. Maar ik geloof dat je dat al aan het doen bent?

True; vandaar mijn laatste vraag een paar posts terug.

[Confusion]

.oisyn schreef op maandag 12 mei 2008 @ 04:07:
Euhm, een hashtable is in theorie gewoon O(1) hoor. Net als een array, waarbij je zegt dat je het Nde element wil hebben. Dan is je key gelijk aan de index. In een hashtable is niet N je index in de array, maar juist hash(key). Bij een goede uniforme hash functie en een table die groot genoeg is is een lookup daardoor O(1).

Als ik een generieke hashtable met 1000 elementen heb en ik wil het element met hash 485759303 hebben: welk algoritme gaat me dan in O(1) vertellen of die hash er in zit? De table is niet 485759303 (*2) entries groot.

[ Voor 64% gewijzigd door Confusion op 12-05-2008 11:00 ]

[Creepy]

Het zal wel aan mij liggen maar als je een hashtable hebt met ruimte voor 1000 entries en je hashtable gebruikt een hash die 485759303 oplevert dan is het hoog tijd voor een ander algoritme.

Tuurlijk, het kan niet altijd precies O(1) zijn omdat je met een stukje overloop zit die normaal gesproken linear doorzocht moet worden maar zoals .oisyn al aangeeft: in theorie is het O(1). In de praktijk kan het neerkomen op O(1) + O(n) voor de overloop van de betreffende hash. En als je overloop per hash te groot wordt wordt het tijd voor een ander hash algoritme.

[Confusion]

Creepy schreef op maandag 12 mei 2008 @ 11:34:
Het zal wel aan mij liggen maar als je een hashtable hebt met ruimte voor 1000 entries en je hashtable gebruikt een hash die 485759303 oplevert dan is het hoog tijd voor een ander algoritme.

java.util.HashMap<String, String>? Een string kan gerust een hash van 485759303 hebben. Als ik wil weten of de string met hash 485759303 als key in de HashMap voorkomt, dan zal het algoritme toch O(log(N)) keer moeten kijken (als het bijvoorbeeld een binary search doet naar de hash)?

[xces]

Stel je wilt een folder deleten. Deze folder heeft ongetwijfeld subfolders en files. Zou je dan een iterator maken die door de folder heen loopt, van ieder gevonden item een object aanmaakt en vervolgens op dat object de "delete" functie aanroept (en dus recursief werkt)?

Of zou je gewoon een query doen, welke files/folders eronder horen, en deze in het object wat je aangemaakt hebt verwijderen, vervolgens een delete in SQL uitvoeren? (dus alles in hetzelfde object houden)?

OO gezien moet je voor optie 1 kiezen, memory gezien moet je voor optie 2 kiezen.. Hoe denken jullie erover?

[Zoijar]

Je moet natuurlijk wel over dezelfde big-O praten. Meestal heb je het over amortized O(1); als ik tienduizend searches doe in een hashtable, waar kom je dan op uit. Dan heb je nog best- en worst-case; best-case vind je het element meteen in O(1) en worst case moet je een hele bucket napluizen in O(log n) (of zelfs O(n)). Sommige hashmap implementaties zoeken sowieso in O(log n), zoals bijvoorbeeld de STL std::map.

Ik heb ook ooit deze nog geimplementeerd: Wikipedia: Cuckoo hashing Traag om te bouwen, maar dan ontzettend snel om te zoeken.

Als PHP te traag is, dan schrijf je het toch gewoon in C++

[ Voor 20% gewijzigd door Zoijar op 12-05-2008 12:05 ]

[xces]

Dat O(..) is best wel interessant, heeft dat ook een naam?

[Zoijar]

O(..) is "big-O" en hash tables zijn "amortized constant time", of "amortized O(1)"

[Creepy]

Confusion schreef op maandag 12 mei 2008 @ 11:45:
[...]

java.util.HashMap<String, String>? Een string kan gerust een hash van 485759303 hebben. Als ik wil weten of de string met hash 485759303 als key in de HashMap voorkomt, dan zal het algoritme toch O(log(N)) keer moeten kijken (als het bijvoorbeeld een binary search doet naar de hash)?

Maar dan ga je er vanuit dat de hashfunctie die de HashMap gebruikt voor het opzoeken van elementen dezelfde hash gebruik als String.hashCode(); De hashfunctie moet je laten afhangen van de capaciteit van de HashMap en niet van 1 vaste hashfunctie omdat de hashfunctie direct de index moet opleveren van het te zoeken item.

http://java.sun.com/j2se/...pi/java/util/HashMap.html
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method.

Aangezien de documentatie aangeeft dat de performance afhankelijk is van de capaciteit en de loadfactor en het automatisch aanpassen van de capaciteit indien de loadfactor is bereikt gevolgd door een rehash lijkt me dat dan ook dat de HashMap een eigen hashfunctie gebruikt en niet de .hashCode() direct gebruikt voor het zoeken.

[ Voor 8% gewijzigd door Creepy op 12-05-2008 13:13 ]

[Verwijderd]

Creepy schreef op maandag 12 mei 2008 @ 13:07:
Aangezien de documentatie aangeeft dat de performance afhankelijk is van de capaciteit en de loadfactor en het automatisch aanpassen van de capaciteit indien de loadfactor is bereikt gevolgd door een rehash lijkt me dat dan ook dat de HashMap een eigen hashfunctie gebruikt en niet de .hashCode() direct gebruikt voor het zoeken.

Dat klopt. Er wordt eerst een widening algoritme gebruikt om voor matige hashcode implementaties te compenseren en vervolgens simpelweg een bitwise AND uitgevoerd op lengte van de array.

[.oisyn]

Zoijar schreef op maandag 12 mei 2008 @ 11:59:
Sommige hashmap implementaties zoeken sowieso in O(log n), zoals bijvoorbeeld de STL std::map.

std::map is geen hashmap. Er is niets dat jou de mogelijkheid geeft om een hashfunctie te definieren. Misschien ben je in de war met stdext::hash_map?

Confusion schreef op maandag 12 mei 2008 @ 10:05:
[...]

Als ik een generieke hashtable met 1000 elementen heb en ik wil het element met hash 485759303 hebben: welk algoritme gaat me dan in O(1) vertellen of die hash er in zit? De table is niet 485759303 (*2) entries groot.

hash % table_size, waarbij table_size typisch een priemgetal is. 2003 bijvoorbeeld, in het geval van 1000 elememten. De index is dus 1758.

Confusion schreef op maandag 12 mei 2008 @ 11:45:
[...]

java.util.HashMap<String, String>? Een string kan gerust een hash van 485759303 hebben. Als ik wil weten of de string met hash 485759303 als key in de HashMap voorkomt, dan zal het algoritme toch O(log(N)) keer moeten kijken (als het bijvoorbeeld een binary search doet naar de hash)?

Dat is al helemaal O(1). Want dan kijk je gewoon of de entry op 485759303 % table_size bezet is of niet. Je wilt immers weten of er al een entry met die hash bestaat. Niet of jouw string erin staat. En idd, een andere string kan theoretisch dezelfde hash opleveren. Dus als je wilt weten of jouw string erin staat, moet je de bucket op positie 485759303 % table_size nog doorzoeken (waar worst-case alle elementen terecht zijn gekomen, maar als dat vaak voorkomt is je hash functie gewoon slecht gekozen voor jouw usecase).

Verwijderd schreef op maandag 12 mei 2008 @ 13:18:
[...]
Dat klopt. Er wordt eerst een widening algoritme gebruikt om voor matige hashcode implementaties te compenseren en vervolgens simpelweg een bitwise AND uitgevoerd op lengte van de array.

Alleen als de array-lengte een macht van twee is natuurlijk. Is dat in de java hashmap gegarandeerd? Bovendien gebruik je dan alleen maar de onderste bits van een hash en gooi je de rest weg. Dat lijkt me nou niet echt bepaald optimaal. Vandaar de modulus en een priemgetal (of de vorm 2ⁿ-1) als arraygrootte.

[ Voor 51% gewijzigd door .oisyn op 12-05-2008 13:45 ]

[Zoijar]

.oisyn schreef op maandag 12 mei 2008 @ 13:36:
std::map is geen hashmap. Er is niets dat jou de mogelijkheid geeft om een hashfunctie te definieren. Misschien ben je in de war met stdext::hash_map?

Ja, dat was een beetje ongelukkig uitgedrukt. Ik bedoelde een map voor key/value pairs. Boost heeft idd een echte hashmap, die nu is opgenomen in de TR1 standard library in <unordered_map>.

---

Cuckoo hashing heeft overigens worst-case O(1) lookups, oftewel een constant time lookup wordt gegarandeerd. Insertions zijn amortized O(1). Het enige nadeel is dat de load-factor maar 49% is. De theorie van hash tables kan best ingewikkeld zijn, en er zijn meerdere factoren die meespelen.

[Confusion]

Creepy schreef op maandag 12 mei 2008 @ 13:07:
[...]
De hashfunctie moet je laten afhangen van de capaciteit van de HashMap[..]

.oisyn schreef op maandag 12 mei 2008 @ 13:36:
hash % table_size, waarbij table_size typisch een priemgetal is. 2003 bijvoorbeeld, in het geval van 1000 elememten. De index is dus 1758.

Ah, werkt dat zo, dat wist ik niet. Ik had altijd begrepen dat zoeken in een hashtable O(log(N)) was en had daar uit afgeleid dat er dus echt gezocht moest worden met binary search of slimmer algoritme. Ik heb mijn oorspronkelijke post aangepast.

[xces]

Ik vind het heel fijn dat jullie door discusieren over algoritmes, maar zou in dat geval niet de topictitel aanepast moeten worden, we aan nu een beetje off topic.. Daarnaast zie ik niet echt antwoorden op mijn vragen terwijl die volgens mij voor jullie echt een eitje zijn

[Voutloos]

ACM schreef op maandag 12 mei 2008 @ 09:08:
[...]
Helaas kent PHP zelf geen andere datastructuren dan de multifunctionele array/hashmap/queue/list.

Klopt, dus idd minder relevant voor PHP, alhoewel genoeg mensen op een stupide manier met arrays omgaan.

Dat ben ik met je eens en toch ook weer niet. In mijn ervaring bleken bepaalde zaken die ik eerder afgedaan zou hebben als microoptimalisatie behoorlijk wat impact te hebben. Met name kijkend naar geheugengebruik en de daarbij behorende performance.

Ik heb elke micro optimalisatie ook wel eens zelf toegepast en je kan er best wat aan hebben, maar ik had het idee dat ts iig in eerste instantie nog toe was aan de grotere optimalisaties, of in ieder geval weten waar de bottleneck echt zit, zoals jij ook in je 1e post stelt.

De standaard optimalisatie tips (zoals de meeste punten uit deze top 40) zijn niet echt interessant om te bespreken. Kwestie van 1x dat lijstje lezen en je weet wat zaken om op te letten. Overigens staat er wel iets over de magic methods als __get en __set en staat profilen op een te lage plaats 41.

xces schreef op maandag 12 mei 2008 @ 09:48:
De MPTT klasse had (schrik niet) 63 meg geheugen nodig, om een tree met 4000 entrys te initializeren (grofweg 20 folders en de rest files). OO-gezien heb ik het goed aangepakt, met recursie bedoel ik. ....

Profile, of meet zelf op de kritieke punten het geheugengebruik. Je zal wellicht bij een aantal operaties verbaasd zijn over hoe het geheugengebruik opeens fors toe neemt. Zo kan je zien of je bijvoorbeeld het eea moet opruimen cq uberhaupt overbodig aanmaakt, of dat je bijvoorbeeld bepaalde tussenresultaten iets anders moet doen. Leuke voorbeelden zijn grote strings/arrays waar je eerst een kopie van maakt en pas veel later het origineel van weggooit etc.

[Creepy]

xces schreef op dinsdag 13 mei 2008 @ 07:51:
Ik vind het heel fijn dat jullie door discusieren over algoritmes, maar zou in dat geval niet de topictitel aanepast moeten worden, we aan nu een beetje off topic..

Vindt je? Het gebruikte algoritme of de gebruikte class kan een hoop schelen qua geheugengebruik of que performance of etc. etc. Dat sluit precies aan bij "wat is sneller/beter en waarom". Daarnaast zijn dit soort zaken echt niet PHP specifiek.

Daarnaast zie ik niet echt antwoorden op mijn vragen terwijl die volgens mij voor jullie echt een eitje zijn

No offence maar als je met een concreet probleem zit schaar dat dan niet onder het kopje "kennis delen" of "wat is sneller/beter en waarom". Open dan gewoon een nieuw topic.

xces schreef op maandag 12 mei 2008 @ 09:48:
[...]


Correct. Ik zal je vertellen; sinds mijn servers over zijn gegaan van PHP4 naar PHP5 ben ik eigenlijk alles gaan ombouwen naar objecten. Alles, alsin: Veel van mijn sites gebruiken basecode die ik in de laatste jaren heb "verzameld" en geoptimaliseerd. Zo heb ik een validatieklasse, date time parsing functies wrapper om phpmailer heen die automatisch images attached, enzovoorts. De nieuwe sites, krijgen dan meteen een opfriscursus voor de achterliggende code

De MPTT klasse had (schrik niet) 63 meg geheugen nodig, om een tree met 4000 entrys te initializeren (grofweg 20 folders en de rest files). OO-gezien heb ik het goed aangepakt, met recursie bedoel ik.

Recursie heeft niks met OO te maken, recursie kan ook prima in niet OO talen.

Maar aan de andere kant heb ik het ook weer fout gedaan; Zoals je misschien weet werkt MPTT met "left" en "right" waardes. Ook al voegde ik vanuit het object weer nieuwe childnodes toe, wijzigde ik de waardes van de parent niet, dus het parent object was zoiezo geen reeele weergave van de huidige staat in de database.

4000 objecten in het geheugen bijhouden is ook helemaal niet interessant, want ik deed er toch niets mee. Ook het weergeven van deze objecten doe ik nu altijd zo (pseudo):

code:

list($arrData, $intCount) = $object->loadChildren(<van>, <tot>, <extra_where>, <extra_order>);

Vervolgens assignde ik het object aan de template, wat als voordeel oplevert dat je het object in zijn geheel in de template kunt gebruiken. Aan de andere kant is dat natuurlijk juist iets wat je wilt vermijden, aangezien de template voor DISPLAY gebruikt moet worden en eigenlijk niets anders moet doen dan kant en klare data aanleveren.

Moraal van het verhaal; ik "dacht" dat OO in PHP dé oplossing was, maar dit blijkt bij dit soort scenario's dus weer niet het geval;

Ook hier ontgaat mij weer wat je bedoelt met OO. Het feit dat jij 4000 objecten zo lang mogelijk in het geheugen houdt die je niet allemaal nodig hebt heeft niks met een OO opzet te maken. Dat je zoveel geheugen nodig hebt ligt aan je algoritme, niet aan het wel of niet OO opzetten van je code.

Ik denk dat je de verkeerde conclusie trekt...

hoe gebruiken jullie objecten in PHP dan?
Een verbeterslag zou kunnen zijn dat ik geen objecten maar slechts een array met DIE waardes die ik ook nodig heb meegeef aan het script. Dit scheelt natuurlijk geheugen, maar dan stap je weer van objecten af..

Ook dit ontgaat me weer. Je kan prima object georienteerd werken en alleen de zaken die je nodig hebt inladen. Dat je een array van object hebt maakt je code echt niet minder OO dan een oplossing die bijv. een Tree bijhoudt met met Objecten

[xces]

Creepy schreef op dinsdag 13 mei 2008 @ 09:03:
Vindt je? Het gebruikte algoritme of de gebruikte class kan een hoop schelen qua geheugengebruik of que performance of etc. etc. Dat sluit precies aan bij "wat is sneller/beter en waarom". Daarnaast zijn dit soort zaken echt niet PHP specifiek.

Vandaar dat ik aangaf of de topic titel niet aangepast moest worden, want dat is nu nog een specifieke PHP titel

Creepy schreef op dinsdag 13 mei 2008 @ 09:03:No offence maar als je met een concreet probleem zit schaar dat dan niet onder het kopje "kennis delen" of "wat is sneller/beter en waarom". Open dan gewoon een nieuw topic.

De TS is veroorzaakt door mijn "probleem" waar ik later op uitwijdde, sorry daarvoor

Creepy schreef op dinsdag 13 mei 2008 @ 09:03:

[...]

Ook dit ontgaat me weer. Je kan prima object georienteerd werken en alleen de zaken die je nodig hebt inladen. Dat je een array van object hebt maakt je code echt niet minder OO dan een oplossing die bijv. een Tree bijhoudt met met Objecten

Verschil tussen PHP en Java/.NET/Delphi is in mijn ogen dat je een script doorloopt van boven naar onderen. In .NET en/of java heb je een "main()" thread, en in PHP gewoon "het script zelf". Ik denk dat ik te ver doordraai door ALLES in objecten te willen doen terwijl dit (inderdaad) niet helemaal nodig is.

[Voutloos]

xces schreef op dinsdag 13 mei 2008 @ 09:18:
Verschil tussen PHP en Java/.NET/Delphi is in mijn ogen dat je een script doorloopt van boven naar onderen. In .NET en/of java heb je een "main()" thread, en in PHP gewoon "het script zelf".

Totaal niet interessant 'verschil'. Het belangrijkste verschil is dat PHP geen application scope heeft en dat je elke hit weer alle objecten mag aanmaken.

Ik denk dat ik te ver doordraai door ALLES in objecten te willen doen terwijl dit (inderdaad) niet helemaal nodig is.

Het punt is juist dat enkel alles in objecten stoppen niet de ware OO gedachte is. Bekijk de voordelen van OO tov imperatieve werkwijze eens, daar staat niet tussen 'foo is nu een object ipv een scalar! '

[SchizoDuckie]

xces schreef op dinsdag 13 mei 2008 @ 09:18:
[...]

Verschil tussen PHP en Java/.NET/Delphi is in mijn ogen dat je een script doorloopt van boven naar onderen. In .NET en/of java heb je een "main()" thread, en in PHP gewoon "het script zelf". Ik denk dat ik te ver doordraai door ALLES in objecten te willen doen terwijl dit (inderdaad) niet helemaal nodig is.

Euh. die vergelijking snap ik even niet... Bij een java/.NET/Delphi prog heb je ook gewoon een 'startpunt' vanwaaruit je code kan vertakken toch

Verder, het is helemaal niet erg om *alles* in objecten te willen doen in PHP, alleen de flexibiliteit van PHP geeft je gewoon de optie om dingen die niet in objecten hoeven gewoon plat te scripten.
Zo hoef ik bijv. geen object wat de juiste code aanslingert a.d.h.v. een URL rewrite. Ik explode $_SERVER['REQUEST_URI'] op / (gofweg) en de array die daar uit komt trap binnen plugins door een switch() heen. Binnen die plugins worden meestal pas een paar objecten gebruikt om taken te vervullen. Lekker flexibel icm een __autoload, en je voorkomt dat je overbodige meuk init waardoor de request tijd lekker kort blijft

[xces]

Oke, point taken. Mijn nieuwe "implementatie" is af, d.w.z. zonder __get en __set enzovoorts. Verschil is er wel (20 seconden sneller) maar het kan sneller..

Om het even over algoritmes te hebben; ben ik van mening dat ik iets fout doe. MPTT heeft een drietal querys nodig om een object in te voegen / child toe te voegen aan een array. Helaas kun je de eerste 2 niet combineren..
- "left" gat maken
- "right" gat maken
- insert uitvoeren

Momenteel loop ik echter door een directory en voeg ik ieder object direct toe, en als ik een folder tegenkom doe ik een recursie in die folder. Het leek mij de beste manier. Echter heb ik nu een nieuw idee, wat misschien beter is, aangezien het "herbouwen" van een tree toch bijna nooit gebeurd.

Wat als ik nu eerst ga kijken hoeveel objecten er in een folder zitten (files/folders) deze stop ik in een array, vervolgens onderaan maak ik 1x ruimte (ik weet immers hoe groot de array is die ik weg wil schrijven) en vervolgens voeg ik ieder record toe. Vele malen sneller, ik zal eens kijken hoe ver ik daarmee kom.

[SchizoDuckie]

Waarom maak je ingodesnaam van elke 'file' in de directory een object dan ? Ik zou gewoon de hele directory structuur (dmv een recursieve glob loop) in een geneste array opslaan en een soort van 'wrapper' object maken wat die structuur manipuleert/uitleest.

Overigens, als je het met zulke bizarre arrays nodig hebt dat het sneller gaat worden als je em van te voren allocate in PHP zal je waarschijnlijk nog wel iets fout niet helemaal optimaal doen. Aangezien je met web bezig bent moet je imo ook altijd de keuze maken tussen welk niveau van OO ga ik gebruiken en mem usage/cpu usage van je webserver. Volgens mij gaat die van jou het nu namelijk ook niet leuk vinden als je tegelijktijdig ineens een hoop request binnenkrijgt...

[ Voor 29% gewijzigd door SchizoDuckie op 13-05-2008 10:18 ]

[xces]

SchizoDuckie schreef op dinsdag 13 mei 2008 @ 10:11:
Waarom maak je ingodesnaam van elke 'file' in de directory een object dan ? Ik zou gewoon de hele directory structuur (dmv een recursieve glob loop) in een geneste array opslaan en een soort van 'wrapper' object maken wat die structuur manipuleert/uitleest.

Vwb optimalisatie van mijn "algoritme" blijkt eerdergenoemde methode zeker zijn vruchten af te werken. Van 140 seconden terug naar 4,5 seconden om alle 4000 objecten in de database te stoppen (inclusief ophalen van ctime, mtime, atime, width/height igv een plaatje). Lijkt me vrij netjes niet? Overigens werk ik nu niet meer met objecten, maar sla ik de tijdelijke data op in arrays.

[ Voor 15% gewijzigd door xces op 13-05-2008 14:25 ]