Le jeudi 29 novembre 2012 10:48:45 UTC+1, Sebastian Krebs a écrit : > > > > 2012/11/29 Nicolas <nicolas....@gmail.com <javascript:>> > >> *Hashmap*, finally after a strange wakeup in the middle of the night, i >> researched how the array is implemented in php. I taked my last hour (or >> two) to read wikipedia and the php sources (wikipedia, >> <http://en.wikipedia.org/wiki/Hash_table> >> zend_hash.h<https://github.com/php/php-src/blob/master/Zend/zend_hash.h#L261> >> and >> zend_hash.c<https://github.com/php/php-src/blob/master/Zend/zend_hash.c#L909> >> ). >> >> If i see this >> graph<http://upload.wikimedia.org/wikipedia/commons/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg>, >> >> from wikipedia, the hash isn't use to find the keys, but to find the value >> (the cost is O(1) at less to find the value *linked *to a key). >> >> If i see the code and particulary the following, i have the impress that >> the hash table is a linked list pointer which iterate on a linked list >> of item (call >> bucket<https://github.com/php/php-src/blob/master/Zend/zend_hash.h#L54>with >> key, value). If the cost was only O(1), the following function >> zend_hash_index_exists should just return value of a structure indicated >> by a pointer, in this case the cost seems to be O(1) to O(n) following the >> place of the key, for me *ulong h* is the hash : >> >> >> ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h) >> { >> uint nIndex; >> Bucket *p; >> IS_CONSISTENT(ht); >> nIndex = h & ht->nTableMask; >> p = ht->arBuckets[nIndex]; >> while (p != NULL) { >> if ((p->h == h) && (p->nKeyLength == 0)) { >> return 1; >> } >> >> p = p->pNext; >> } >> >> return 0; >> } >> >> Finally i'm not completly sure how php implements each array, but it >> seems to me that O(1) isn't right. And in fact even if a hash simplify the >> search a hash can't return a memory place with a data structure or a >> type by itself. It must be finded in a linked list before. >> > > Why? :confused: A hashmap is a direct-memory structure. It's like "item > you are looking for is at [offset] + [hash]%[maxBuckets]". This can be > itself a pointer and I can directly jump to that address. There is > absolutely no iteration required (and useful). >
After search all power of 2 superior at *32768 *cause many collisions because all hash_key become indenticals, (hack here<http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf>, the correctif don't change behavior, just protect Globals). If you simplify all, forget the limit cases (hash collision, full hashmap), you find O(1) as complexity, but i cannot prevent me to think that collisions appear and the O(1), transforms itself in O(n*x) (with x as collision rate as average case, and if you considere x as a constant... The hash_code creation is too O(n) regarding n as the key length, it isn't nothing. Consequently to the collision, the first key in the map have a directly access by hash, with more chance than the key at the end of the map. I think always that a big array is a sensible data, which could be design with attention, this was just my term here. Thanks to php to hide that :) But should we forget there pointers, >> structures and others c behaviors? >> > > We should, because we are not developing in C. Don't give them too much > value, they are implementation details of the underlying engine and usually > there a negliable against what your application _really_ does (especially > IO). We could even take registers and such into account, but where should > it end? > I'm not completly agree, you should think about your underlying dependencies, with references and registers as you say, but too with all the libraries directly in your workflow : how curl works, if you make http/ftp request, how database works (even with an orm<http://docs.doctrine-project.org/en/2.1/reference/batch-processing.html> )... And as the C is the php base, with the C too. A little *joke *test, view many times but surelly exact https://gist.github.com/4176171, and showing flagrants differences if you take time to test it (one to 4). And the response is in thinking about pointer and affectation prefer than php variables. I agree that many others thing are importants (efficiency, custumer satisfactions, tests, reusability...), but we cannot trash all optimisation. > > >> However, the autoloading take time and was clearly showed on my profiler >> traces, and even if this seems not that symfony will win many speed, it >> will loose nothing and *gain *in the same time a *little speed* and *clarity >> with hermetic environnements.* >> > > Be careful with such statements: It may loose stability by introducing > complexity. The 1% is it definitely not worth. Be careful with micro > optimizations! > 1. I'm not sure hermetic and definable environnements in composer and consequently in class map could be consider as a complexity (seems easy coding), neither a micro optimization and this was the main code objective. 2. Surelly but no code optimization is a worst case particularly *when the computer speed don't growth and so many posts shoot symfony for its speed. T *oo many in my mind, this is the reason which could me to begin a discussion on speed. On this, good weekend, maybe at the next week. > > >> * >> * >> Le mercredi 28 novembre 2012 17:05:15 UTC+1, Sebastian Krebs a écrit : >> >>> As long as a classmap is a map, it's a hashmap and therefore the access >>> is usually O(1), meaning: Doesn't care, where the corresponding class >>> appears within the list. >>> >>> >>> 2012/11/28 Nicolas <nicolas....@gmail.com> >>> >>>> Tests maded with apc, and even with apc the class isn't load if the >>>> file isn't load, so apc don't avoid the autoload mecanismus. >>>> >>>> For the differences beetween dev and prod environnement, i think the >>>> number of classes isn't the only point, the order is to a problem, as >>>> symfony is at the end of the class map (the order is alphabetical), so >>>> each >>>> symfony class take more than 1500 comparisons strings to just load the >>>> classes at every requests. >>>> >>>> Le mercredi 28 novembre 2012 06:46:55 UTC+1, Cameron Junge a écrit : >>>> >>>>> Were the tests performed with & without APC? APC will load the file >>>>> straight from memory in a compiled form, so should help speed things up >>>>> if >>>>> the original tests were performed without it. Most production >>>>> environments >>>>> use a cache. >>>>> >>>>> Building an optimized classmap for each environment would probably >>>>> only alter a small number of classes, so not sure what benefit there is >>>>> in >>>>> having multiple versions. For example, the difference between dev & >>>>> production on one of my projects would probably be a few 10s or so >>>>> classes... and some of them will be the automatic exchange of a debug >>>>> class >>>>> & the original class. >>>>> >>>>> Cameron >>>>> >>>>> On Saturday, November 24, 2012 5:15:44 PM UTC+13, Nicolas wrote: >>>>>> >>>>>> Hello, >>>>>> >>>>>> As i play all this afternoon with xdebug, i could see that* the >>>>>> class loader* take time and mainly *is called many times (~900 by >>>>>> request)*. >>>>>> >>>>>> As i wanted* to improve the speed of a production environnement,* i >>>>>> made tests and watch in details as the code is called. >>>>>> >>>>>> After take improvement give by the docs and finally by the command >>>>>> >>>>>>> php composer.phar dump-autoload --optimize >>>>>> >>>>>> >>>>>> I* remove *from the file *vendor/composer/autoload_classmap.php* >>>>>> produced *the tests classes* (252 on 2890, less than 1%) and run >>>>>> tests with and without there changes. The result of the tests are in >>>>>> a gist <https://gist.github.com/4137837>. The gain is a little more >>>>>> than one percent on a complex page and less significant on a hello world >>>>>> page. >>>>>> >>>>>> My personnals conclusions are the array class's map should be >>>>>> optimised. Solutions could be than : >>>>>> >>>>>> - A *arbitrary* *environnements *should be defined* in composer*to >>>>>> correspond to applications and produce specific class_loader files >>>>>> purposing *to reduce the array size* >>>>>> >>>>>> >>>>>> - The* order of calling frequencies* should impose* t*he *order >>>>>> in composer requirements* which should save it in *the order of >>>>>> the classes's map *file (vendor/composer/autoload_[**env** >>>>>> ]_classmap.php)*, to reduce the search time* >>>>>> >>>>>> I have begin to post there solutions in a composer issue created by >>>>>> Seldaek few month ago. But as i maded tests on symfony, as i have a >>>>>> little voice in the symfony community, and i think you could think >>>>>> better, >>>>>> and certainly produce smarter code than me about there behaviors with >>>>>> better acuity (mostly as i see the time i spend to make this mail >>>>>> and so... and the hour it is). >>>>>> >>>>>> So good night, or have nice day, >>>>>> >>>>>> Best Regards, >>>>>> >>>>>> Nicola >>>>>> >>>>>> PS: Very thanks for all you works, symfony and composer and all the >>>>>> library become more and more nice to use. >>>>>> >>>>> -- >>>> If you want to report a vulnerability issue on symfony, please send it >>>> to security at symfony-project.com >>>> >>>> You received this message because you are subscribed to the Google >>>> Groups "symfony developers" group. >>>> To post to this group, send email to symfon...@googlegroups.com >>>> >>>> To unsubscribe from this group, send email to >>>> symfony-devs...@**googlegroups.com >>>> >>>> For more options, visit this group at >>>> http://groups.google.com/**group/symfony-devs?hl=en<http://groups.google.com/group/symfony-devs?hl=en> >>>> >>> >>> >>> >>> -- >>> github.com/KingCrunch >>> >>> -- >> If you want to report a vulnerability issue on symfony, please send it to >> security at symfony-project.com >> >> You received this message because you are subscribed to the Google >> Groups "symfony developers" group. >> To post to this group, send email to symfon...@googlegroups.com<javascript:> >> To unsubscribe from this group, send email to >> symfony-devs...@googlegroups.com <javascript:> >> For more options, visit this group at >> http://groups.google.com/group/symfony-devs?hl=en >> > > > > -- > github.com/KingCrunch > > -- If you want to report a vulnerability issue on symfony, please send it to security at symfony-project.com You received this message because you are subscribed to the Google Groups "symfony developers" group. To post to this group, send email to symfony-devs@googlegroups.com To unsubscribe from this group, send email to symfony-devs+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/symfony-devs?hl=en
