[issue38045] Flag instance creation is slow

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

The fast method to check if the value is a power of two:

not value & (value - 1)

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38045] Flag instance creation is slow

[Antony Lee]

New submission from Antony Lee :

Consider the following example

from enum import Flag
F = Flag("F", list("abcdefghijklm"))
for idx in range(2**len(F) - 1):
F(idx)

creating all possible combos of 13 flags, so 8192 instances (yes, I know the 
instances are cached later, but the initial cost is still significant).  
Locally, this takes over 4.5s to execute; profiling shows that ~30% of that 
time is spent executing enum._is_power_of_two(!):

def _power_of_two(value):
if value < 1:
return False
return value == 2 ** _high_bit(value)

Indeed, replacing the implementation of _power_of_two by

import math
_powers_of_two = {
2 ** i for i in range(math.ceil(math.log2(sys.maxsize)) + 1)}
def _power_of_two(value):
return (value in _powers_of_two if value <= sys.maxsize
else value == 2 ** _high_bit(value))

shaves off ~30% of the runtime (obviously this won't help for huge 
(>sys.maxsize) flag values, but these are rarer I would think).

An even better fix, I think, would be for Flag to cache `flags_to_check` 
(updating it at the same time as `_value2member_map_`) instead of recomputing 
it each time in _decompose

flags_to_check = [
(m, v)
for v, m in list(flag._value2member_map_.items())
if m.name is not None or _power_of_two(v)
]

as this actually needlessly introduces quadratic complexity when iterating over 
all possible combos (because the size of _value2member_map_ is growing).  
(Also, it's not actually clear to me how one can end up with unnamed 
power-of-two instances in _value2member_map?)

--
messages: 351244
nosy: Antony.Lee
priority: normal
severity: normal
status: open
title: Flag instance creation is slow
versions: Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com