Fix next_100 pointers

[wakolzin]

The current realization (master branch) of next_100 pointers update slightly constrain splicing stage if we have 101+ entries in queue. More precisely, the last entry in queue will never be chosen as second entry to splice with. For example, in queue contained 101, 102, 103, ..., 200, 201 etc. entries the last entry will always be skipped.

Let's consider the reason. Let queue with queued_paths = n consists of n entries with indices 0..n-1 When queued_paths is 100 we set next_100 pointer to refer on the last element of queue with index = 99 here:

if (!(queued_paths % 100)) {

    q_prev100->next_100 = q;
    q_prev100 = q;

}

Consider queue contains 101 entries with indices 0..100. In splicing stage after this line call, where the random index from 0..100 can be chosen: do { tid = UR(queued_paths); } while (tid == current_entry);

suppose tid is 100. So, we expect to take the entry with index = 100

But, in this line: while (tid >= 100) { target = target->next_100; tid -= 100; }

the expression target = target->next_100 give us entry with index = 99.

[lszekeres]

@lszekeres and @jonathanmetzman do any of you understand this?

Having a hard time too (not because of the patch though :)

But, in this line: while (tid >= 100) { target = target->next_100; tid -= 100; }

the expression target = target->next_100 give us entry with index = 99.

If this is where the issue is, would it be possible to fix it at this line perhaps? Or alternatively could you leave a short explanation comment in the code at the changed line (if (!(queued_paths % 100))) on why we check for queued_paths % 100 == 1? Thanks!

[wakolzin]

@lszekeres I've added explanation comment.