Re: [E-devel] Edje data speedup
On Fri, 2 Mar 2007 09:12:54 -0600 "Nathan Ingersoll" <[EMAIL PROTECTED]> babbled: > On 3/2/07, Tilman Sauerbeck <[EMAIL PROTECTED]> wrote: > > > > IIRC there's one global "data" section, and every collection/group does > > have its own "data" section, too. So we can't get away with a single > > hash table. Not that it matters much :) > > Right, the proposed change was only for the global data section and > not the group data sections. My thinking was that with per-group data > collections, you are much less likely to have many items in the list > since they are a much smaller scope for each. actually i have an idea - just encode the hash keys. group names must be unique - thus you can have "group_name/data_key" and still have 1 hash per edje file (file data can be just "/data_key"), thus only overhead of 1 hash per file, and then just start adding nodes on load (add all the file data nodes to start with, then add all the group data nodes the first time they are loaded). > - > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys-and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > ___ > enlightenment-devel mailing list > enlightenment-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/enlightenment-devel > -- - Codito, ergo sum - "I code, therefore I am" -- The Rasterman (Carsten Haitzler)[EMAIL PROTECTED] 裸好多 Tokyo, Japan (東京 日本) - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On 3/2/07, Simon TRENY <[EMAIL PROTECTED]> wrote: > > Maybe the hash could be created only if there is a certain number of > items in the data section. For example, if there are more than 20 > items, you build the hash, otherwise you keep the linked-list. And that > could be applied for both global and group data-sections. > > Simon That's a possibility, but it will probably require different thresholds for the global and group sections since 1-2 KB of memory per group could add up quickly. - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On Fri, 2 Mar 2007 09:12:54 -0600, "Nathan Ingersoll" <[EMAIL PROTECTED]> wrote : > On 3/2/07, Tilman Sauerbeck <[EMAIL PROTECTED]> wrote: > > > > IIRC there's one global "data" section, and every collection/group > > does have its own "data" section, too. So we can't get away with a > > single hash table. Not that it matters much :) > > Right, the proposed change was only for the global data section and > not the group data sections. My thinking was that with per-group data > collections, you are much less likely to have many items in the list > since they are a much smaller scope for each. Maybe the hash could be created only if there is a certain number of items in the data section. For example, if there are more than 20 items, you build the hash, otherwise you keep the linked-list. And that could be applied for both global and group data-sections. Simon > > - > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to > share your opinions on IT & business topics through brief surveys-and > earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > ___ enlightenment-devel > mailing list enlightenment-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/enlightenment-devel > - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On 3/2/07, Tilman Sauerbeck <[EMAIL PROTECTED]> wrote: > > IIRC there's one global "data" section, and every collection/group does > have its own "data" section, too. So we can't get away with a single > hash table. Not that it matters much :) Right, the proposed change was only for the global data section and not the group data sections. My thinking was that with per-group data collections, you are much less likely to have many items in the list since they are a much smaller scope for each. - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On 3/2/07, The Rasterman Carsten Haitzler <[EMAIL PROTECTED]> wrote: > On Thu, 1 Mar 2007 00:23:17 -0600 "Nathan Ingersoll" <[EMAIL PROTECTED]> > babbled: > > cool! nice work on the profiling. > > anyway - you hit a usage case i didn't expect/intend for the edje file data - > i > expected it to be used rarely so it wouldn't be a bottlneck. hashes are fairly > big as they need to allocate space for at least N bucket points to start with, > so if you only have a few items, i decided no hash was the way to go - given > the above assumption, it saved memory and would be ok. 1 hash per file though > isn't too bad - and i think that'd be acceptable, but you can also have object > data (done the same way) and then per object you'd need a hash (well per > source > object - each instance cah share the source config for the group object). no > need to break the format here - just populate the hash on load from the list > (then even free up the list and empty it). :) That's fine, this is actually what I've already implemented. Though I have not made that change for the object data sections as that could result in a lot more hashes (and all N buckets) being created. Thanks, Nathan - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
Brian Mattern [2007-03-01 15:34]: > On Thu, Mar 01, 2007 at 09:35:13PM +0100, Tilman Sauerbeck wrote: > > ACK. I believe raster's reasoning for using lists in various spots that > > would intuitively like to be hashes was the size of the entries that are > > stored. IIRC evas/ecore_evas also use lists to store key/value userdata. > > Yes, but the assumption is that there won't be many data nodes. If there > ARE (like in ewl themes which map generic keys to actual groups), then > you get the performance hit. So, its a tradeoff. This change (as far as Yes, I know and agree. Just wanted to explain the original reasoning :) > I understand) would be a single hash per edje file (~1K). (What's the typical > size of an edje file in memory?) E's theme (typically) a single file, so > this shouldn't be too bad. IIRC there's one global "data" section, and every collection/group does have its own "data" section, too. So we can't get away with a single hash table. Not that it matters much :) > It could also only allocate the hash for files that actually have data. Yep, thought of that, too. Regards, Tilman -- A: Because it messes up the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? pgpXGM0txkAQh.pgp Description: PGP signature - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On Thu, 1 Mar 2007 00:23:17 -0600 "Nathan Ingersoll" <[EMAIL PROTECTED]> babbled: cool! nice work on the profiling. anyway - you hit a usage case i didn't expect/intend for the edje file data - i expected it to be used rarely so it wouldn't be a bottlneck. hashes are fairly big as they need to allocate space for at least N bucket points to start with, so if you only have a few items, i decided no hash was the way to go - given the above assumption, it saved memory and would be ok. 1 hash per file though isn't too bad - and i think that'd be acceptable, but you can also have object data (done the same way) and then per object you'd need a hash (well per source object - each instance cah share the source config for the group object). no need to break the format here - just populate the hash on load from the list (then even free up the list and empty it). :) > Doing some profiling, I noticed that I was seeing a fair amount of > overhead (19.9% of the test apps completion time) coming from strcmp, > and in particular from calls to edje_file_data_get. This isn't > completely unexpected as EWL uses data keys in the edje to map widgets > to edje collections, but it had me wondering why there were so many > comparisons relative to other hot paths in the code. > > The problem became clear when I saw how data lookups were being done, > a linear scan of a list doing strcmp against each key in the list > until a match was found. With each search being O(n), this could add > up quickly. Since we are using key/value pairs for the data > association, a hash seemed more appropriate. > > To test this without breaking the file format, I added a cache to the > edje file struct and populated it immediately after reading the file > by moving data out of the list and into the hash. Using the new hash I > re-ran my test and saw an improvement of 18.5%, and basically > eliminating almost the entire time spent in edje_file_data_get. > > While I don't expect to see a huge improvement, this would be more > efficient using a hash directly in the eet. The downside would be that > compatibility would be broken for existing edje's. > > So that finally brings me to my questions: what is the current policy > on breaking edje compatibility? and does anyone have an objection to > moving the data storage to be a hash rather than a list? > > Thanks, > Nathan > > - > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys-and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > ___ > enlightenment-devel mailing list > enlightenment-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/enlightenment-devel > -- - Codito, ergo sum - "I code, therefore I am" -- The Rasterman (Carsten Haitzler)[EMAIL PROTECTED] 裸好多 Tokyo, Japan (東京 日本) - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On 3/1/07, Tilman Sauerbeck <[EMAIL PROTECTED]> wrote: > > ACK. I believe raster's reasoning for using lists in various spots that > would intuitively like to be hashes was the size of the entries that are > stored. IIRC evas/ecore_evas also use lists to store key/value userdata. Is there extra storage overhead in the eet files for storing hash entries beyond storing the key/value pairs of a list? I haven't looked at this closely yet, but I will before making any further changes. The way I currently have it implemented is not a terrible trade-off if it saves space in the files. As rephorm pointed out, this will be a small runtime impact of approximately 1-2kb per edje file. The edje file's are cached so multiple references to an edje file will refer to the same hash table. And because of how evas hash tables work (NULL pointer for empty hash tables), it would only allocate the hash if there are data entries present. - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On Thu, Mar 01, 2007 at 09:35:13PM +0100, Tilman Sauerbeck wrote: > ACK. I believe raster's reasoning for using lists in various spots that > would intuitively like to be hashes was the size of the entries that are > stored. IIRC evas/ecore_evas also use lists to store key/value userdata. Yes, but the assumption is that there won't be many data nodes. If there ARE (like in ewl themes which map generic keys to actual groups), then you get the performance hit. So, its a tradeoff. This change (as far as I understand) would be a single hash per edje file (~1K). (What's the typical size of an edje file in memory?) E's theme (typically) a single file, so this shouldn't be too bad. It could also only allocate the hash for files that actually have data. rephorm - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
Christopher Michael [2007-03-01 05:01]: > Nathan Ingersoll wrote: > > Doing some profiling, I noticed that I was seeing a fair amount of > > overhead (19.9% of the test apps completion time) coming from strcmp, > > and in particular from calls to edje_file_data_get. This isn't > > completely unexpected as EWL uses data keys in the edje to map widgets > > to edje collections, but it had me wondering why there were so many > > comparisons relative to other hot paths in the code. > > > > The problem became clear when I saw how data lookups were being done, > > a linear scan of a list doing strcmp against each key in the list > > until a match was found. With each search being O(n), this could add > > up quickly. Since we are using key/value pairs for the data > > association, a hash seemed more appropriate. > > > > To test this without breaking the file format, I added a cache to the > > edje file struct and populated it immediately after reading the file > > by moving data out of the list and into the hash. Using the new hash I > > re-ran my test and saw an improvement of 18.5%, and basically > > eliminating almost the entire time spent in edje_file_data_get. > > > Just my 2 cents, but with gains like that how can we NOT use a hash :) ACK. I believe raster's reasoning for using lists in various spots that would intuitively like to be hashes was the size of the entries that are stored. IIRC evas/ecore_evas also use lists to store key/value userdata. Regards, Tilman -- A: Because it messes up the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? pgpP1SKGH0lHg.pgp Description: PGP signature - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On Thu, Mar 01, 2007 at 08:13:19AM -0600, Nathan Ingersoll wrote: > On 3/1/07, Christopher Michael <[EMAIL PROTECTED]> wrote: > > > > Just my 2 cents, but with gains like that how can we NOT use a hash :) > > Right, we're going to use a hash one way or another, just a question > of if we want to break the edje format to do it. :) In this case, old files will just need to be recompiled (edje_recc should do it), so I don't see a problem. At some point we'll need to start versioning the file format and keeping the code compatible with old versions, but that can probably wait until release. (e.g. stay compatible with release versions, but not the various iterations in between). rephorm - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
On 3/1/07, Christopher Michael <[EMAIL PROTECTED]> wrote: > > Just my 2 cents, but with gains like that how can we NOT use a hash :) Right, we're going to use a hash one way or another, just a question of if we want to break the edje format to do it. :) > Such is the way with pre-alpha code...things break. Theme/edj authors > will just have to deal with it I suppose. I'm sure at some point there > will be another breakage after this one before things start to settle. Probably will be another break down the line, but at some point there will have to be a version freeze on the format. Just trying to be certain that's not now. > I say if it's more efficient, go for it...tho imho we should wait until > "old man" has a chance to chime in :) Sure, though he has been very busy lately and if there is a consensus on the current format state, I don't think we need to bother him with it. Thanks for the feedback. Nathan - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
Re: [E-devel] Edje data speedup
Nathan Ingersoll wrote: > Doing some profiling, I noticed that I was seeing a fair amount of > overhead (19.9% of the test apps completion time) coming from strcmp, > and in particular from calls to edje_file_data_get. This isn't > completely unexpected as EWL uses data keys in the edje to map widgets > to edje collections, but it had me wondering why there were so many > comparisons relative to other hot paths in the code. > > The problem became clear when I saw how data lookups were being done, > a linear scan of a list doing strcmp against each key in the list > until a match was found. With each search being O(n), this could add > up quickly. Since we are using key/value pairs for the data > association, a hash seemed more appropriate. > > To test this without breaking the file format, I added a cache to the > edje file struct and populated it immediately after reading the file > by moving data out of the list and into the hash. Using the new hash I > re-ran my test and saw an improvement of 18.5%, and basically > eliminating almost the entire time spent in edje_file_data_get. > Just my 2 cents, but with gains like that how can we NOT use a hash :) > While I don't expect to see a huge improvement, this would be more > efficient using a hash directly in the eet. The downside would be that > compatibility would be broken for existing edje's. > Such is the way with pre-alpha code...things break. Theme/edj authors will just have to deal with it I suppose. I'm sure at some point there will be another breakage after this one before things start to settle. > So that finally brings me to my questions: what is the current policy > on breaking edje compatibility? and does anyone have an objection to > moving the data storage to be a hash rather than a list? > I say if it's more efficient, go for it...tho imho we should wait until "old man" has a chance to chime in :) > Thanks, > Nathan > Cheers, dh - Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV ___ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
