[tor-bugs] #6538 [Tor Client]: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more time-invariant

[Tor Bug Tracker & Wiki]

#6538: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more
time-invariant
-------------------------+--------------------------------------------------
 Reporter:  nickm        |          Owner:                    
     Type:  enhancement  |         Status:  needs_review      
 Priority:  normal       |      Milestone:  Tor: 0.2.3.x-final
Component:  Tor Client   |        Version:                    
 Keywords:               |         Parent:                    
   Points:               |   Actualpoints:                    
-------------------------+--------------------------------------------------

Comment(by nickm):

 rransom points out that he has some integer scaling code that's better
 than what I wrote:
 {{{
 13:48 < rransom> Was there a reason to use llround (and add autocrap goo
 to
                  check for it) instead of my approach to int64_t-izing the
                  bandwidths?
 13:50 < nickm> Argh.  Context-switching.  I had thought that my approach
 was to
                int64_t-ize: that is, to move the bandwidth array to
 uint64_t
                earlier in the computation and get "double" out of the
 picture
                entirely by the time that we did the "choose one randomly
 by
                weight" computation.
 13:51 < nickm> The reason I want the computation to be (array of uint64_t,
                length, entropy) -> index is that I trust myself to
 reasoning
                about this stuff much better when all values are integers.
 13:51 < nickm> *to reason
 13:52 < rransom> You used llround on (approximately) the values that would
 have
                  been in the array of doubles before. I rescaled them to a
                  total bandwidth around 2^61 and justcasted to int64_t .
 13:54 < nickm> A decent idea; maybe we should do that too.  Why 2^61?
 13:55 < rransom> Because it's big, but not close enough to 2^63 that I
 would
                  have to think carefully about whether the roundoff errors
                  could overflow and really break things.
 14:01 < nickm> mind  if I C&P the above to the bug report?
 14:01 < rransom> Go ahead.
 }}}

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/6538#comment:11>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online