Remove asyncio.run call in dlog.py #393

Activity

1. AddressXception

   added this to the 🦖 Bowser Jr. v1.3.0 milestone on Jul 21, 2021
2. AddressXception

   added

   bugSomething isn't workingSomething isn't working

   code owner onlyOnly for Code OwnerOnly for Code Owner

   on Jul 21, 2021
3. danwallach commented on Jul 21, 2021

   

   danwallach

   on Jul 21, 2021

   Collaborator

   More actions

   That's weird. Also, for what it's worth, the code isn't quite correct for concurrent execution. Once it acquires the lock, it should make a second check to see if the result is already saved. I found that bug when I was rewriting it in Kotlin.

   While you're dorking with dlog.py, you should also consider making it return Optional[int] rather than int as a circuit-breaker against bogus inputs which don't have a result.

   When I did this, it caused all sorts of changes downstream, so you may prefer to raise an exception and have appropriate try/catch blocks.

   __dlog_cache: Dict[ElementModP, int] = {ONE_MOD_P: 0}
   __dlog_max_element = ONE_MOD_P
   __dlog_max_exponent = 0
   __DLOG_MAX = 100_000_000
   
   __dlog_lock = asyncio.Lock()
   
   
   def discrete_log(e: ElementModP) -> Optional[int]:
       """
       Computes the discrete log (base g, mod p) of the given element,
       with internal caching of results. Should run efficiently when called
       multiple times when the exponent is at most in the single-digit millions.
       Performance will degrade if it's much larger.
   
       If the exponent is enormous (greater than a hundred million or so), then
       this function will give up and return `None`, which the caller should
       check.
   
       Note: *this function is thread-safe*. For the best possible performance,
       pre-compute the discrete log of a number you expect to have the biggest
       exponent you'll ever see. After that, the cache will be fully loaded,
       and every call will be nothing more than a dictionary lookup.
       """
       global __dlog_cache
   
       # no need for mutually exclusive access when reading from the cache
       if e in __dlog_cache:
           return __dlog_cache[e]
       else:
           return asyncio.run(__discrete_log_internal(e))
   
   
   async def __discrete_log_internal(e: ElementModP) -> Optional[int]:
       global __dlog_cache
       global __dlog_max_element
       global __dlog_max_exponent
       global __dlog_lock
   
       async with __dlog_lock:
           # We need to check the dict again; it might have changed.
           if e in __dlog_cache:
               return __dlog_cache[e]
   
           g = int_to_p_unchecked(G)
           while e != __dlog_max_element:
               __dlog_max_exponent = __dlog_max_exponent + 1
               if __dlog_max_exponent >= __DLOG_MAX:
                   log_error(f"Discrete log failure: exponent was > {__DLOG_MAX}")
                   return None
               __dlog_max_element = mult_p(g, __dlog_max_element)
               __dlog_cache[__dlog_max_element] = __dlog_max_exponent
   
           return __dlog_cache[__dlog_max_element]
4. AddressXception

   self-assigned this

   on Jul 22, 2021
5. keithrfung

   modified the milestones: 🦖 Bowser Jr. v1.3.0, 🔥 Trogdor v1.2.3 on Jul 22, 2021
6. AddressXception commented on Jul 23, 2021

   

   AddressXception

   on Jul 23, 2021

   Last edited by AddressXception

   ContributorAuthor

   More actions

   ahh good catch. We have a couple of items on the docket to deal with caching state a bit better in the library anyway so I added your suggestion to double check the cache but im going to leave the out of bounds for now.
7. AddressXception

   closed this as completedin #405on Aug 3, 2021