Month: May 2020

May 29, 2020

Erratum in Timescale Functions for Parallel Memory Allocation [Li et. al., 2019]

Elias Neuman-Donihue, University of Rochester, May 2020

A small correction to Li et. al.’s paper: in section 3.2, the length of a time window is defined as “its end time minus its start time plus one.” However, in section 3.2.1, there is a reference to “windows of length k from 0 \leq k \leq n,” the lower bound of which refers to windows with their end index before their start. This also leads to some mathematical inconsistencies in sections 3.2.1 and 3.2.2.

One such error is the calculation of reuse(1): by the stated definition, an interval of length k=1 has only one allocation, so the reuse should be one if the window also contains a matching free operation and 0 otherwise. Therefore, since there are a total of n windows of length 1, the average reuse of all such windows should be:

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}

However, by the formulae stated in 3.2.2:

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=1)s_i - \sum_{i=1}^{m}I(e_i-s_i=1)(s_i + 1) + 2\sum_{i=1}^{m}I(e_i-s_i=1)}{n}

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=1)}{n} \neq \frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}

In order to standardize the equations with the provided definition of window length, a few changes must be made:

In Eq. 1 and Eq. 2, every instance of e_i - s_i \le k should instead read e_i - s_i < k

Then in Eq. 2,
Z(k)= \frac{\sum_{i=1}^{m}I(e_i - s_i < k) \cdot k}{n-k+1}

The recursive equations should then read

X(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)s_i

X(k) = X(k-1) + \sum_{i=1}^{m}I(s_i\ge n-(k-1)) + \sum_{i=1}^{m}I(e_i-s_i+1=k)min(n-k, s_i)

Y(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)e_i

Y(k) = Y(k-1) + \sum_{i=1}^{m}I(e_i\le k-1) + \sum_{i=1}^{m}I(e_i-s_i+1=k)max(k, e_i)

Z(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)

Z(k) = Z(k-1) + \sum_{i=1}^{m}I(e_i-s_i < k) + \sum_{i=1}^{m}I(e_i-s_i+1=k) \cdot k

May 5, 2020

Good luck penny

(Sent to my class on the exam day)

NY Times collects and publishes New York city stories submitted by its readers at https://www.nytimes.com/column/metropolitan-diary.  The May 3 entry was Christopher Fryer who remembered “joys of city life walking every day from our apartment on the Upper West Side through Central Park, and then down Sixth Avenue to my office at 46th Street”, found “a shining Lincoln head on the penultimate step”, “paused to pick it up, being careful not to impede either the people coming up behind me or those who were heading down into the station”, and “a man on his way down the stairs spoke without breaking stride.

“Hey,” he said. “ I saw one of those at 125th Street. If you hurry you can probably get that one, too.”

With that piece, other readers made comments, including this one by Susan Hayes from NJ:

Re finding pennies and other coins, I was always told that they had to be face up to be “good luck.”  I read somewhere a long time ago about a kind soul who would turn coins over when found face down so the next person to see them would have good luck, so I do that. It’s a little like being Santa Claus.

This is yet another proof of the CSC 200H theme: even good luck requires collaboration.