View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0000701 | LDMud 3.5 | Efuns | public | 2009-11-04 03:39 | 2018-01-30 03:59 |
| Reporter | Gnomi | Assigned To | zesstra | ||
| Priority | normal | Severity | minor | Reproducibility | have not tried |
| Status | resolved | Resolution | fixed | ||
| Platform | i686 | OS | Debian GNU/Linux | OS Version | 4.0 |
| Target Version | 3.5.0 | Fixed in Version | 3.5.0 | ||
| Summary | 0000701: sizeof(mapping) is expensive | ||||
| Description | When a mapping is given to sizeof() all its keys get checked for references to destructed objects. This is needed to give an exact answer but it makes sizeof() O(n) instead of O(1), which is quite unexpected. So it would be nice to optimize that. Suggestions: a) Have a flag that indicates whether this mapping has any keys referencing objects (objects, closures). b) Have some kind of a time stamp of the last check. The global time stamp must then be incremented on each destructed object. | ||||
| Tags | No tags attached. | ||||
|
|
Ugly thought: If we add a signed integer to mappings as timestamp, we may combine them both by using the sign bit to indicate keys referencing objects. I just saw, that C99 changed time_t and only states that time_t must a numerical type, so that one would not work in this case. (I guess, we may see quite a lot of bugs in all sorts of programs soon. *g*) |
|
|
I didn't mean some time() like time stamp, but more something like a counter that is incremented on each object destruction (because otherwise it's hard to distinguish when destruction and mapping check happened in the same second). |
|
|
Yes, right, time_t was a first reaction upon time stamp. ;-) Something like p_int is anyway more suitable (although I think, a int32_t would be completely sufficient, we don't need 8 bytes on x86_64). Then we could just set it to -1 in mappings without keys referencing objects and the counter otherwise... BTW: Maybe we should add a note about the O(n) in the manpage? |
|
|
I will have a look into this and implement Gnomis suggestion first. I am not sure if we should use the part of my suggestion to track if a mapping references objects by using a bit from the counter (e.g. negative value in the mapping -> no objects referenced). This would save some more time, but then we have to check the destructed-object-counter for overflow each time we increment it. And we have to keep the marker in the mapping uptodate all the time (all places which enter or delete values). Do you think it is worth it? On the other hand: this optimization would probably be done in check_map_for_destr(), which means we save time not only in sizeof(), but a lot places more: copy(), deep_copy(), +, -, [], resize_mapping(), compact_mapping(), m_indices(), m_values(), walk_mapping(), filter_mapping(), m_reallocate(), unmkmapping(), save_mapping(). |
|
|
For a 'this mapping references objects' marker in general we have to take object the values into account as well, not only keys. In addition to checking all keys upon addition (which is IMHO not to complicated), we have to check all assignments to mapping values. I am reluctant to do that. Besides the work it seems very easy to miss one place and that would probably introduce nasty crashes, because suddenly we have destructed objects somewhere in mappings. |
|
|
I think the functionality of check_map_for_destr should be splitted. In most cases we only need to check the keys. I think only cleanup_vector() needs also to check the values. So it may be better two have one fast function for the keys and the slow function for the cleanup routines. |
|
|
Good idea. I committed a series of experimental patches in r2861-r2864: 1) introduce the 'timestamp' Gnomi suggested (BTW: Because currently the overhead is 4 Bytes per Mapping, we might think about using a uint16_t instead of uint32_t, if we are confident that the risk of destroying exactly 65536 objects between two calls to check_map_for_destr_keys() for a specific mapping is low enough. But I am unsure about this.) 2) split check_map_for_destr() into check_map_for_destr_keys() and check_map_for_destr_values() with the timestampf from 1) being in check_map_for_destr_keys(). 3) changed some check_map_for_destr() to check_map_for_destr_keys() which are IMHO riskless, including in sizeof(). I still have to check other users of check_map_for_destr() in more detail later. BTW: If you like to comment on the changes in a specific commit or specific file in a commit: You might do so at http://github.com/zesstra/ldmud-mirror/commits/master as I today found out... Quite fascinating. |
|
|
I don't like to introduce this changes in 3.3.x, so I am moving all this to 3.5.x only if nobody objects. Then I will only attach a note about the O(n) behaviour in then sizeof() manpage in 3.3.x. |
|
|
I believe, this is done for now. I hope, I did not introduce new bugs in the process... ;-) |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2009-11-04 03:39 | Gnomi | New Issue | |
| 2009-11-04 05:00 | zesstra | Note Added: 0001599 | |
| 2009-11-04 05:10 | Gnomi | Note Added: 0001600 | |
| 2009-11-04 06:20 | zesstra | Note Added: 0001601 | |
| 2010-02-13 16:08 | zesstra | Note Added: 0001724 | |
| 2010-02-13 16:08 | zesstra | Assigned To | => zesstra |
| 2010-02-13 16:08 | zesstra | Status | new => assigned |
| 2010-02-13 18:29 | zesstra | Note Added: 0001725 | |
| 2010-02-14 06:10 | Gnomi | Note Added: 0001726 | |
| 2010-02-14 16:37 | zesstra | Note Added: 0001729 | |
| 2010-07-14 02:38 | zesstra | Target Version | => 3.3.720 |
| 2010-07-22 02:02 | zesstra | Project | LDMud 3.3 => LDMud 3.5 |
| 2010-07-22 02:04 | zesstra | Note Added: 0001891 | |
| 2010-07-22 02:04 | zesstra | Product Version | 3.3.719 => |
| 2010-07-22 02:04 | zesstra | Target Version | 3.3.720 => 3.5.0 |
| 2011-11-22 22:28 | zesstra | Note Added: 0002085 | |
| 2011-11-22 22:28 | zesstra | Status | assigned => resolved |
| 2011-11-22 22:28 | zesstra | Fixed in Version | => 3.5.0 |
| 2011-11-22 22:28 | zesstra | Resolution | open => fixed |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 2b5b766e |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master c9b50c91 |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 5cfa493e |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 9a7e667e |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master bc863aae |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master a104c8a5 |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 64b17c83 |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 80a6bb07 |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 4098cb02 |
| 2012-06-04 20:48 | zesstra | Source_changeset_attached | => ldmud.git master 30721ff6 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 2b5b766e |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master c9b50c91 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 5cfa493e |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 9a7e667e |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master bc863aae |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master a104c8a5 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 64b17c83 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 80a6bb07 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 4098cb02 |
| 2018-01-29 18:59 | zesstra | Source_changeset_attached | => ldmud.git master 30721ff6 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 2b5b766e |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master c9b50c91 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 5cfa493e |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 9a7e667e |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master bc863aae |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master a104c8a5 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 64b17c83 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 80a6bb07 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 4098cb02 |
| 2018-01-29 21:57 | zesstra | Source_changeset_attached | => ldmud.git master 30721ff6 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 2b5b766e |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master c9b50c91 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 5cfa493e |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 9a7e667e |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master bc863aae |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master a104c8a5 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 64b17c83 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 80a6bb07 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 4098cb02 |
| 2018-01-30 03:59 | zesstra | Source_changeset_attached | => ldmud.git master 30721ff6 |
