

        <cite>Conor</cite>
      <time>0:00</time>
      <p>
          O   of   n   where   n   is   the   number   of   elements,   and   then   you&#39;re   gonna   have   to   store   like   a   min   heap,   right?   Yeah.   So   it&#39;s   actually   it&#39;s   actually   gonna   be   like   uh   O   of   N   log   K,   I   think.   Uh,   because   in   it   like   you   can&#39;t   just   store   the   top   K   values,   you   have   to   store   them   in   such   a   way   that   you&#39;re   able   to   pop   off   efficiently.   Welcome   to   ADSP   the   podcast   episode   187,   recorded   on   June   11th,   2024.   My   name   is   Connor,   and   today   with   my   co-host   Bright,   we   continue   our   chat   about   implementing   the   Top   K   algorithm,   aka   Nth   element   in   parallel.
      </p>

        <cite>Bryce</cite>
      <time>0:47</time>
      <p>
          Did   did   you   did   you   listen   to   my   uh   the   my   last   message   that   I   sent   you   yet?
      </p>

        <cite>Conor</cite>
      <time>0:53</time>
      <p>
          Yes,   I   did.   So   I   guess   we   just   released   episode   185,   right?   And   that   was   phone   tag.   Yeah.   And   then   the   Friday   that   we   released,   which   is   a   couple   days   ago   now,   because   it&#39;s   Tuesday,   you   recorded   half   of   a   phone   tag.   I   did   listen   to   that,   but   I&#39;ve   been   so   crazy   busy   for   like   the   last   three   days   or   whatever,   since   uh   Friday.
      </p>

        <cite>Bryce</cite>
      <time>1:17</time>
      <p>
          I   have   yet   to   act   more   than   the   last   three   days,   buddy.
      </p>

        <cite>Conor</cite>
      <time>1:20</time>
      <p>
          Three   or   four   days.   You   wouldn&#39;t   even   Yeah,   it&#39;s   it&#39;s   it&#39;s   been   nuts.   And   so   the   to   answer   your   question,   yes,   I   have   listened   to   it,   but   no,   I   have   not   recorded   my   half   to   that.
      </p>

        <cite>Bryce</cite>
      <time>1:32</time>
      <p>
          Well,   you&#39;re   gonna   have   to   get   around   to   that.
      </p>

        <cite>Conor</cite>
      <time>1:33</time>
      <p>
          And   I   guess   the   listener   now,   this   is   what   episode   187,   so   they&#39;re   they&#39;ve   already   heard   both   your   half   that   is   currently   as   of   this   recording,   has   been   recorded,   and   they   will   have   also   heard   my   half   that   has   not   yet   been   recorded   as   of   this   recording.   But   by   the   time   the   listener   has   heard   this,   all   of   the   recordings   and   publishings   will   have   happened.
      </p>

        <cite>Bryce</cite>
      <time>1:56</time>
      <p>
          So   so   where   where   where   else   have   you   been?   Because   you&#39;ve   been   busy,   you&#39;ve   been   like   on   the   road,   right?
      </p>

        <cite>Conor</cite>
      <time>2:01</time>
      <p>
          Uh   not   really.   I   mean,   I&#39;ve   been   stopping   back   in   Toronto.   So   I   was   at   first   I   was   at   uh   a   KraftConf.   It&#39;s   a   conference   in   Budapest,   Hungary.   That   was   just   a   two-day   conference,   phenomenal   conference.   Um,   really   cool   because   I   got   to   meet   I   think   you&#39;ve   probably   met   Kevlin   Henney   a   bunch   of   times   because   you&#39;ve   gone   to   ACCU.
      </p>

        <cite>Bryce</cite>
      <time>2:20</time>
      <p>
          I   have,   yeah,   he&#39;s   cool.
      </p>

        <cite>Conor</cite>
      <time>2:20</time>
      <p>
          But   I&#39;ve   actually   never,   and   he&#39;s   one   of   my   favorite   speakers.   I&#39;ve   I&#39;ve   never   actually   met   him   in   person.
      </p>

        <cite>Bryce</cite>
      <time>2:25</time>
      <p>
          Uh   you   know   who   we   should   have   on   the   podcast.   You   know   who   I   would   be   hilarious   on   the   podcast.
      </p>

        <cite>Conor</cite>
      <time>2:30</time>
      <p>
          Oh   man,   that&#39;s   why   I   haven&#39;t   Yeah,   that   guy   is   such   a   good   smoker.   My   brain   is   not   working   right.   Uh   I&#39;m   on   like   three   hours   of   sleep   after   a   lot   of   travel,   so   uh   bear   with   me,   listeners,   over   the   next   two   episodes   here.   But   yes,   we   should   definitely   have   him   on.   He&#39;s   he   said   one   of   my   favorite   things   in   a   couple   of   his   talks.   He   actually   said   it   at   in   one   of   his   talks   at   KraftConf,   which   I   think   it   was   entitled   Um   Testing   with   Guts,   G-U-T-S,   Good   Unit   Tests.   And   he   I   heard   this   for   the   first   time,   and   he   he   basically   said,   It   really   bothers   me   when   people   say   it&#39;s   just   semantics.   And   immediately   I   was   like,   absolutely.   Oh   my   god,   this   I&#39;ve   been   thinking   this   like   my   whole   life.   Finally,   do   people   do   people   say   that?   Yeah,   and   it&#39;s   like   think   about   what   you&#39;re   saying.   It&#39;s   it&#39;s   only   I&#39;ve   never   heard   the   meaning   of   the   words.   Like,   it&#39;s   like,   what   are   we   talking   about?
      </p>

        <cite>Bryce</cite>
      <time>3:22</time>
      <p>
          I   did   have   a   conversation,   and   I   I   suspect   it   was   one   of   my   coworkers,   and   if   the   coworker   is   listening,   I   apologize   in   advance.   But   I   was   having   some   conversation   with   somebody   where   they   kept   saying   semantics,   but   they   meant   syntax.
      </p>

        <cite>Conor</cite>
      <time>3:37</time>
      <p>
          Oh.
      </p>

        <cite>Bryce</cite>
      <time>3:37</time>
      <p>
          Um   like   it   wasn&#39;t   like   an   extended   thing,   but   it   was   like   over   the   quiz   like   two   minutes,   and   this   doesn&#39;t   mean   like   they   said   something   to   the   effect   of   like,   well,   it&#39;s   just   semantics,   and   I&#39;m   like,   wait,   I   think   you   mean   it&#39;s   just   syntax.
      </p>

        <cite>Conor</cite>
      <time>3:46</time>
      <p>
          Yeah.
      </p>

        <cite>Bryce</cite>
      <time>3:47</time>
      <p>
          Like   I&#39;ve   never   heard   people   say   it&#39;s   just   semantics.
      </p>

        <cite>Conor</cite>
      <time>3:48</time>
      <p>
          Oh   no,   people   say   it   is.
      </p>

        <cite>Bryce</cite>
      <time>3:50</time>
      <p>
          It&#39;s   that&#39;s   exactly   the   point.   It&#39;s   like   uh   I   think   I   think   it&#39;s   a   I   think   that   it   is   a   phrase   that   come   that   uh   comes   from   non-programmer   speak,   right?   Like   it   it   like   I   could   imagine   I   I   can   think   outside   of   the   context   of   programming,   like   the   phrase   it&#39;s   just   semantics   is   like   a   common   phrase,   which   kind   of   means   like   it&#39;s   just   details,   right?
      </p>

        <cite>Conor</cite>
      <time>4:11</time>
      <p>
          Yeah.
      </p>

        <cite>Bryce</cite>
      <time>4:11</time>
      <p>
          And   so   people   might   be   saying   that   to   mean   it&#39;s   just   details,   whereas   I   think   I   I   don&#39;t   know,   I&#39;m   a   spec,   I&#39;m   like   a   programming   language   spec   person,   so   so   so   maybe   maybe   I   have   a   warped   perspective   on   this.   But   uh   I   think   most   programmers   will   would   not   would   would   interpret   that   differently.   But   I   think   it&#39;s   just   a   common   phrase   in   like   the   English   language   in   general.
      </p>

        <cite>Conor</cite>
      <time>4:33</time>
      <p>
          Yeah.   And   I   think   it&#39;s   similar   to   when   it&#39;s   like   a   different   way   of   saying   tomato   tomato,   which   I   also   take   issue   with.   Yeah.   Because   nobody   says   tomato.
      </p>

        <cite>Bryce</cite>
      <time>4:43</time>
      <p>
          Like   tomato,   your   program   has   undefined   behavior.   Tomato.
      </p>

        <cite>Conor</cite>
      <time>4:50</time>
      <p>
          And   uh   anyways,   we&#39;ll   we&#39;ll   definitely   get   Kevin   on.   I   think   he&#39;d   be   a   blast   to   chat   with.   And   then   after   that,   I   was   at   Should   I   should   I   email   him?   What?
      </p>

        <cite>Bryce</cite>
      <time>5:01</time>
      <p>
          You   want   me   to   email   him?
      </p>

        <cite>Conor</cite>
      <time>5:02</time>
      <p>
          Yeah,   sure.   You   can   email   him   right   now.
      </p>

        <cite>Bryce</cite>
      <time>5:04</time>
      <p>
          Like   before   we   forget,   yeah.   Yeah,   well   I   mean,   not   not   like   right   now,   but   I&#39;ll   start   the   draft   of   the   email.
      </p>

        <cite>Conor</cite>
      <time>5:09</time>
      <p>
          Sounds   good.   You   heard   it   here   first,   folks.   ADSP,   probably   before   episode   200.   We&#39;ll   have   Kevlin   on.
      </p>

        <cite>Bryce</cite>
      <time>5:15</time>
      <p>
          See,   see,   but   the   pro   the   problem   now   is   that   like   if   he   if   he   uh   if   he   rejects   us,   you&#39;re   gonna   have   to   cut   all   this   out.
      </p>

        <cite>Conor</cite>
      <time>5:21</time>
      <p>
          No,   no,   no.   He   I   mean,   it&#39;s   a   bad   look.   It&#39;s   a   bad   look   because   we&#39;re   I&#39;m   I&#39;m   I&#39;m   a   big   fan,   you   know.
      </p>

        <cite>Bryce</cite>
      <time>5:27</time>
      <p>
          So   uh   I   I   I   have   a   follow-up   for   one   of   our   past   episodes   uh   where   we   talked   about   uh   top   K   algorithms   and   we   talked   about   um   uh   radix   partitioning,   and   uh   I   mentioned   that   I   was   chatting   with   my   our   coworker   Elias,   um,   and   he   wrote   me   on   Slack   um   and   he   said,   maybe   one   remark   on   why   an   LSD   Ratex   partitioning   pass   doesn&#39;t   work.   An   LSD   partitioning   pass   tells   you   nothing   about   the   final   rank   of   an   item   because   you&#39;re   just   looking   at   the   least   significant   part.   This   partitioning   pass   is   only   helpful   to   resolve   ties   between   items   that   compare   equal   on   all   the   more   significant   digits.   At   this   point,   you   just   don&#39;t   know   yet   whether   there   are   ties   on   the   more   significant   digits   because   you   are   yet   to   look   at   those.   Remember,   this   is   why   LSD   Radix   sort   requires   stable   partitioning   passes,   while   the   MSD   doesn&#39;t,   unless   you   want   a   stable   sort.   Uh   and   then   he   gave   an   example   that&#39;s   going   to   be   hard   for   me   to   verbalize.   Um   but   uh   I   think   that   that&#39;s   uh   uh   a   pretty   good   uh   uh   uh   explanation   of   like   what   we   we   talked   about   this,   like   why   why   do   we   do   LSD   for   the   radix   sort   versus   for   the   uh   like   versus   it   being   problematic   for   uh   the   radix   partition.   And   so   oh   he   writes   at   the   at   the   bottom   of   his   example   um   that   the   MSD   radix   sort   uh   gives   uh   however   gives   you   already   some   idea   about   the   final   ranks   of   an   item.   An   item   won&#39;t   cross   the   boundaries   of   the   bucket   it   has   been   assigned   to.   In   subsequent   passes,   it   will   just   refine   its   position   within   the   boundaries   of   its   bucket.
      </p>

        <cite>Conor</cite>
      <time>7:12</time>
      <p>
          So   wait,   how   um   so   that   makes   sense,   but   where   does   this   leave   us   with   respect   to   the   top   K   question?
      </p>

        <cite>Bryce</cite>
      <time>7:19</time>
      <p>
          Well,   I   I   I   think   we   may   have   talked   about   it   on   the   phone   tag   episode,   but   I   I   had   suggested   that   it   may   be   um   it   may   be   worth   it   for   a   uh   Radix   partitioning   algorithm   to   do   a   pre   pass   where   you   you   do   a   max.   And   then   um   the   max   tells   you   how   many   uh   uh   like   w   what   is   the   the   relevant,   the   most   relevant   digit   on   the   on   the   most   significant   side.   And   so   you   like,   you   know,   if   if   your   maximum   integer   is   you   know   like   a   hundred,   then   there&#39;s   a   lot   of   digits   that   you   can   skip   over,   right?   And   so   so   let   so   like   in   this   in   this   it   it   depends   on   on   your   cost   function   of   how   much   uh   uh   well   no   actually   it   doesn&#39;t   because   it&#39;s   not   just   a   computational   cost   thing,   right?   Um   it&#39;s   not   just   the   cost   of   doing   the   extra   passes   that   are   that   uh   you   know   are   maybe   not   so   useful.   Uh   no,   actually   I   think   it   is.   I   guess   it   is.   Um   but   you&#39;re   also   paying   it   would   I   think   you   would   pay   an   additional   cost,   and   the   additional   cost   is   um   like   if   if   your   maximum   integer   if   you&#39;ve   got   like   32-bit   integers   and   the   maximum   integer   in   the   set   that   you&#39;re   partitioning   is   an   integer   that&#39;s   100,   and   you   do   radix   partitioning   starting   with   the   most   significant   digit,   like   the   first   like   more   than   half   passes   is   going   to   put   everything   into   the   first   bucket.   And   I   don&#39;t   know   if   we   do   actual   data   movement   to   put   things   into   buckets,   or   if   we   just   do   it   with   flags.   Um,   but   certainly   it&#39;s   like   a   lot   of   wasted   computation   there,   and   depending   on   how   expensive   those   passes   are,   it   might   make   it   might   be   worth   doing   that   first   like   max   pass.
      </p>

        <cite>Conor</cite>
      <time>9:05</time>
      <p>
          So   essentially   you&#39;re   just   trying   to   you&#39;re   trying   to   take   your   sort   algorithm   and   basically   just   like   minimize   the   amount   of   computation   that   you   would   have   to   do.   But   then   what   happens   when   you   get   like,   you   know,   your   K   is   going   to   be   in   one   of   the   bins?
      </p>

        <cite>Bryce</cite>
      <time>9:20</time>
      <p>
          No,   I&#39;m   I&#39;m   talking   about   specifically   for   partition.
      </p>

        <cite>Conor</cite>
      <time>9:24</time>
      <p>
          Oh,   so   just   for   partition.
      </p>

        <cite>Bryce</cite>
      <time>9:27</time>
      <p>
          Yeah,   right.   Because   for   for   for   as   he   was   explaining,   uh   for   for   a   radix   sort,   like   you&#39;re   sort   of   going   through   everything   anyways,   and   um   uh   uh   like   it&#39;s   it&#39;s   fine   for   the   sort,   for   sort.   It   but   for   partitioning,   like   you   want   to   um   like   split   things   up   into   reasonably   sized   buckets.
      </p>

        <cite>Conor</cite>
      <time>9:50</time>
      <p>
          But   yeah,   so   but   like   that&#39;s   kind   of   like   a   non-deterministic   algorithm,   right?   Based   on   the   distribution   of   values,   if   you&#39;re   looking   for   top   K,   you&#39;re   gonna   have   to   continuously   do   that   partition   uh   until   you&#39;re   able   to   determine   your   your   k   th   value,   which   for   some   which   I   guess   is   what   you&#39;re   saying.   So   up   front,   if   you&#39;re   doing   some   pass   to   get   you   to   the   maximum   or   some   other   like   metadata   on   the   distribution   of   your   values,   you   can   then   make   sure   that   like   in   the   worst   case   you&#39;re   not   just   doing   uh   a   bunch   of   extra   work.
      </p>

        <cite>Bryce</cite>
      <time>10:29</time>
      <p>
          And   it   is   worth   noting   that   Thrust&#39;s   um   Radix   sort   uh   takes   a   bit   like   an   optional   bit   start   and   bit   end   parameter   to   tell   it   for   you   to   tell   it   uh   like   what   uh   you   know   bits   do   you   want   to   actually   sort   of.
      </p>

        <cite>Conor</cite>
      <time>10:48</time>
      <p>
          Ignore   these   bits   because   you   know   they&#39;re   never   used.
      </p>

        <cite>Bryce</cite>
      <time>10:51</time>
      <p>
          Yeah.   Yeah.
      </p>

        <cite>Conor</cite>
      <time>10:52</time>
      <p>
          It&#39;s   still   it&#39;s   still   kind   of   somewhat   unsatisfying   because   of   the   like   uh   I   don&#39;t   know,   non-determinism   of   it.
      </p>

        <cite>Bryce</cite>
      <time>11:03</time>
      <p>
          Yeah,   I   mean   it&#39;s   probably   better   than   sample   sort   though.
      </p>

        <cite>Conor</cite>
      <time>11:07</time>
      <p>
          Yeah,   I   mean   like   it&#39;s   definitely   for   for   a   k   value   that&#39;s   not   sufficiently   small   or   sufficiently   large   to   do   the   either   reduction   or   sort,   it&#39;s   definitely   gonna   be   better   than   doing   a   full-blown   sort.
      </p>

        <cite>Bryce</cite>
      <time>11:19</time>
      <p>
          Yeah.   You   know,   what   we   were   talking   about   last   time   with   um   with   like   the   small   k   case,   um   it   got   me   thinking   a   little   bit   more   that   um   if   k   is   like   uh   small   but   not   small   enough   that   you   would   want   to   pass   it   by   value.   Like   if   k   if   k   is   like   10,   or   okay,   let&#39;s   use   a   simple   example.   If   k   is   one,   you   know,   it&#39;s   just   a   max   reduction.   And   so   like   it&#39;s   pretty   pretty   clear   that   that   you   don&#39;t   need   any   uh   like   like   additional   overhead   or   or   or   anything.   There&#39;s   there&#39;s   no   state   at   all.   Um   if   k   is   two,   you   need   some   state,   right?   Your   your   operator   needs   some   state   to   remember   what   the   the   largest   was   because   it&#39;s   searching   for   the   second   from   largest.
      </p>

        <cite>Conor</cite>
      <time>12:10</time>
      <p>
          Right.   I   mean   technically   uh   max   reduction   also   requires   state,   but   it&#39;s   just   the   accumulator   value.   So   it&#39;s   it&#39;s   it   doesn&#39;t   need   actually   additional   state.
      </p>

        <cite>Bryce</cite>
      <time>12:19</time>
      <p>
          Yeah,   yeah.   And   so   the   the   amount   of   state   that   you   need   grows   linearly.   Um   uh   and   so   like   if   it&#39;s   two,   uh   and   and   because   this   is   an   accumulator   value,   you   know,   you&#39;re   cop   you&#39;re   passing   this   around   by   value.   Um   you   know,   we&#39;re   talking   about   state   that   gets   passed   passed   around   through   the   reduction.   Um   so   it   needs   to   be   something   that   you&#39;re   comfortable   passing   around   by   value   on   the   stack.   If   it&#39;s   two,   you&#39;re   probably   comfortable   with   that.   If   it&#39;s   like   10,   you   know,   maybe   also   that&#39;s   fine.   Um   if   it&#39;s   a   hundred,   that&#39;s   starting   to   get   to   be   a   place   where   that&#39;s   too   large.   Um   but   I   was   thinking   if   the   K   is   100,   is   it   possible   that   there&#39;s   some   algorithm   where   you   have   side   storage   of   uh   uh   you   know   some   array   of   100   elements   and   then   you   have   some   synchronization   protocol   um   for   uh   everybody   to   sort   of   collectively   update   that?   And   is   that   possibly   faster?
      </p>

        <cite>Conor</cite>
      <time>13:15</time>
      <p>
          I   don&#39;t   know.   It&#39;s   an   idea.   I   mean   it&#39;s   very   I   mean   it&#39;s   very   side   effecty,   like   the   very   is   un   unnecessary.   It   it   is   side   effecty,   but   it   could   I   don&#39;t   know,   it   could   be   faster.
      </p>

        <cite>Bryce</cite>
      <time>13:28</time>
      <p>
          But   it   it   could   be   I   mean   what   what&#39;s   the   what&#39;s   the   complexity   and   number   of   comparisons   of   you   know   a   max   reduction.
      </p>

        <cite>Conor</cite>
      <time>13:39</time>
      <p>
          Yeah.   I   mean   yeah,   if   you   if   you   know   you   have   a   s   like   uh   enough   arguments   and   at   a   certain   point   No,   no,   that   was   a   question.
      </p>

        <cite>Bryce</cite>
      <time>13:48</time>
      <p>
          What&#39;s   the   complexity   of   a   max   reduction?
      </p>

        <cite>Conor</cite>
      <time>13:50</time>
      <p>
          Sorry,   what&#39;s   the   complexity   of   a   max   reduction?   Like   a   parallel   max   reduction?
      </p>

        <cite>Bryce</cite>
      <time>13:55</time>
      <p>
          Yeah.   Or   just   no,   just   like   a   max   reduction.
      </p>

        <cite>Conor</cite>
      <time>13:58</time>
      <p>
          It&#39;s   just   uh   line   it&#39;s   linear,   linear   in   time   and   oh   one   in   space.
      </p>

        <cite>Bryce</cite>
      <time>14:03</time>
      <p>
          Right.   And   like   and   like   radix   sort,   which   is   the   special   case,   radix   sort   is   like   what?   Uh   it&#39;s   like   OW   times   n,   uh,   where   n   is   the   number   of   keys   and   w   is   the   key   length,   so   it&#39;s   like   kind   of   uh   kind   of   like   linear   E.   Um   but   like   merge   sort   or   any   anything   for   anything   that   can&#39;t   be   radix   sorted.   Um   what&#39;s   more   merge   sort?   Merge   sort   is   like   uh   you   know,   n   log   n.   Um   so   I   guess   it   is   better,   right?   Right,   right,   right,   right.   Radix   sort   is   worse   complexity-wise.   Because   the   best   of   the   okay,   so   maybe   this   doesn&#39;t   this   never   make   sense,   right?   Because   any   form   of   the   reduction-based   approach   is   gonna   be   linear.   And   if   you   do   something   that   requires   synchronizing   this,   you   know,   global   array,   that&#39;s   gonna   probably   be   expensive.   Um   radix   sort   is   actually   worse   than   like   the   best   case   sorting   algorithms,   right?   Because   it&#39;s   it&#39;s   linear   too.
      </p>

        <cite>Conor</cite>
      <time>15:13</time>
      <p>
          Yeah,   the   only   the   only   thing   that   changes   is   the   the   space   complexity.   It   goes   from   O   of   one   to   O   of   K.
      </p>

        <cite>Bryce</cite>
      <time>15:20</time>
      <p>
          What   do   you   mean?
      </p>

        <cite>Conor</cite>
      <time>15:22</time>
      <p>
          Yeah,   so   like   you&#39;re   definitely   correct   that   a   max   a   max   reduction,   whether   you   are   uh   accumulating   a   single   value,   a   pair   of   values,   or   a   vector   or   array   of   k   values,   it&#39;s   always   linear   in   time   complexity.   Is   that   actually   true?   I   think   for   k   actually,   it   does   change.   It&#39;s   gonna   be   O   of   N   where   n   is   the   number   of   elements,   and   then   you&#39;re   gonna   have   to   store   like   a   min   heap,   right?   Yeah.   So   it&#39;s   actually   it&#39;s   actually   gonna   be   like   uh   O   of   N   log   K,   I   think.   Uh   because   an   like   you   can&#39;t   just   store   the   top   K   values,   you   have   to   store   them   in   such   a   way   that   you&#39;re   able   to   pop   off   efficiently.
      </p>

        <cite>Bryce</cite>
      <time>16:07</time>
      <p>
          So   I   get   I   guess   the   question   here   is   how   fast   of   an   atomic   min   heap   or   max   heap   can   you   implement?
      </p>

        <cite>Conor</cite>
      <time>16:22</time>
      <p>
          I   mean   they   they   are   don&#39;t   they   already   exist?   Is   it   like   C   has   a   priority   queue,   isn&#39;t   that   just   like   a   Yeah,   but   it   needs   to   be   it   needs   to   be   atomic.   Oh,   you   you   mean   for   the   version   where   it&#39;s   it&#39;s   uh   stored   like   outside   of   the   It&#39;s   not   even   it&#39;s   actually   we&#39;re   not   even   talking   about   a   reduction,   right?
      </p>

        <cite>Bryce</cite>
      <time>16:39</time>
      <p>
          At   this   point.   If   like   if   you&#39;re   if   you&#39;re   still   a   reduction.   You   have   sides   stored.   I   mean   No,   it&#39;s   not   it&#39;s   not   it&#39;s   not   really   a   reduction.   It&#39;s   everybody   everybody   is   just   putting   stuff   into   it   into   the   queue.
      </p>

        <cite>Conor</cite>
      <time>16:48</time>
      <p>
          Yeah,   that&#39;s   more   of   like   a   for   each,   but   technically   you   could   like   in   s   in   non-parallel   land,   or   even   in   parallel   land,   you   technically   could   do   it.   You&#39;re   just   like   you&#39;re   suggesting   an   alternative   implementation   where   instead   of   storing   the   state   in   the   accumulator,   you&#39;re   storing   it   outside   and   then   having   some   kind   of   locking   and   synchronizing.   Um   but   you   technically   could   in   C   non-parallel   land   just   like   accumulate   a   priority   queue   or   min   heap   max   heap,   whatever.   And   then   I   think   in   C   17,   I   don&#39;t   fully   I   remember   watching   Ben   Dean&#39;s   talk.   Uh   and   he   he   they   added   like   uh   move   semantics   to   the   accumulators,   so   you   could   actually   like   do   a   reduction   on   a   string   uh   that   was   doing   plus   equals   to   the   string,   and   so   basically   you   know,   adding   characters   or   strings   to   strings,   and   previously   that   was   like   terrible.   It&#39;s   better   to   do   that   in   a   for   loop   because   you&#39;re   gonna   end   up   copying   the   string   every   single   time   if   you   try   and   do   it   inside   of   reduction,   but   then   in   C17   or   20,   I   think   they   added   the   capability   of   uh   the   lambda   that   you&#39;re   passing   to   your   accumulator   reduce,   they   added   the   ability   for   that   to   have   copy   elision.   So   technically,   like   you   could   implement   what   you&#39;re   talking   about   without   storing   it   in   like   side   memory   or   whatever   you   want   to   call   it.   But   yes,   the   version   that   you&#39;re   talking   about.
      </p>

        <cite>Bryce</cite>
      <time>18:12</time>
      <p>
          I&#39;m   not   sure   I   understood   that   explanation.   You   want   to   try   that   again?
      </p>

        <cite>Conor</cite>
      <time>18:15</time>
      <p>
          So   it&#39;s   at   some   point   in   C   17   or   20,   they   basically   added   the   ability   for   the   return   type   of   the   lambda   that   you   passed   to   your   reduction   algorithm   for   it   to   take   advantage   of   copy   elision.   So   like   pre-C   17   or   20,   I   can&#39;t   remember   which   one   it   is.   If   you   are   doing   a   reduction   on   a   string   where   your   initial   string   is   empty   and   you   basically   just   want   to   join   a   bunch   of   strings,   that   was   like   extremely   inefficient   because   every   single   time   you   did   your   plus,   you   would   basically   do   a   copy   of   your   string.   But   like   they   added   an   optimization   where   you   can   take   advantage   of   move   semantics,   a   copy   elision,   where   now   you   actually   can&#39;t   perform   a   reduction   on   like   a   list   of   strings   to   build   up   one   string,   and   you&#39;re   not   gonna   end   up   with   a   bunch   of   copies.   Um   which   for   certain.
      </p>

        <cite>Bryce</cite>
      <time>19:03</time>
      <p>
          So   here&#39;s   here&#39;s   the   problem   with   that.   Um   if   you&#39;re   doing   this   in   parallel,   like   yeah,   it&#39;s   like   I   was   if   you&#39;re   you&#39;re   what   you&#39;re   saying   is   like   if   you   did   like   a   serial   fold   left,   like   you   could   you   could   have   your   state   in   the   the   accumulator   type   and   you   would   never   allocate   uh   more,   right?   Because   you   could   just   always   move   this   accumulator   object   thing,   you&#39;d   never   make   a   copy   of   it.   Yes.   Problem   is   that   we&#39;re   taking   the   input   sequence,   we&#39;re   dividing   it   up,   and   we&#39;ve   got   a   whole   bunch   of   people   operating   in   parallel.
      </p>

        <cite>Conor</cite>
      <time>19:34</time>
      <p>
          Yeah,   yeah.   So   in   parallel,   this   doesn&#39;t   work   at   all.   Yeah.
      </p>

        <cite>Bryce</cite>
      <time>19:37</time>
      <p>
          And   the   the   the   real   problem   actually   is   that   uh   uh   like   you   could   kind   of   do   that   in   parallel,   but   any   form   of   like   like   I   was   thinking,   okay,   what   if   you   had   some   side   array?   Um,   and   then   like   what   if   you   had   like   you   know   one   side   array   per   like   group   of   threads,   but   then   you   have   to   merge   the   side   arrays,   and   then   that&#39;s   annoying,   and   you   know,   like   you   can   do   that   like   the   you   know,   there&#39;s   parallel   merge   algorithms,   but   it&#39;s   it&#39;s   annoying   in   another   cost,   and   then   that   means   like   essentially   you   you   end   up   building   building   the   the   the   uh   something   that   looks   a   lot   like   a   bad   sort.
      </p>

        <cite>Conor</cite>
      <time>20:13</time>
      <p>
          Yeah,   actually   I   was   while   you   were   say   right   before   you   said   that,   I   was   literally   thinking,   actually   I   in   the   yeah,   in   the   parallel   algorithm   where   you   store   K,   when   you   are   combining   the   the   you   know,   min   heaps   or   whatever   in   between   the   chunks,   uh   you&#39;re   gonna   end   up   having   to   do   like   a   std   merge,   which   is   like   an   algorithm   that   like   I&#39;ve   never   used   in   my   life,   but   I   know   exists   for   like   combining   two   sorted   lists.   Yeah.   Yeah.   Yeah.   My   my   point   was   just   that   like   uh   when   you   were   saying   this   isn&#39;t   really   reduction,   I   agree.   It&#39;s   more   of   like   a   for   each   side   effecty   thing.   Yeah.   But   like   in   theory,   you   could   do   this   kind   of   thing   efficiently   in,   like   I   said,   non-parallel   C   land.   Yeah,   I   think   I   think   you   could,   yeah.   I&#39;m   I&#39;m   sure   there&#39;s   a   paper   out   there.   We   should   just   we   should   do   some   research.   Or   we   should   get   the   listener   to   do   some   research.   Go   find   us   the   paper   that   on   on   top   K.   On   parallel   top   K.   I&#39;m   sure   it&#39;s   I&#39;m   sure   it&#39;s   like   it&#39;s   a   common.
      </p>

        <cite>Bryce</cite>
      <time>21:12</time>
      <p>
          There&#39;s   a   bunch   of   uh   uh   papers   out   there,   but   I   don&#39;t   know   that   any   I   don&#39;t   know   that   that   I&#39;ve   seen   any   literature   on   doing   like   a   uh   a   reduction-based   approach   for   like   small   k   and   whether   that   pays   out.   Like   because   like   if   it&#39;s   like   10,   um,   it   starts   to   get   interesting   because   10   is   like   if   let&#39;s   say   let&#39;s   assume   32-bit   numbers,   like   you   know,   10   ints   is   pretty   chunky   to   have   to   to   to   carry   around,   right?   Because   ten   tents   is,   you   know,   for   40   bytes.   Um   but   like   it&#39;s   not   it&#39;s   not   ludicrous   to   to   imagine   just   passing   that   by   value.   So   it   might   pay   off.   And   and   what   may   be   interesting   here   is   that   the   The   payoff   might   be   very   different   for   CPUs   versus   GPUs.   Because   for   CPUs,   you   know,   you&#39;re   gonna   have   order   of   magnitude,   hundreds   of   threads.   So   each   thread   is   gonna   be   doing   a   lot   more   work.   And   so   you&#39;d   have   less   actual   copying   around   of   your   accumulator   type.   And   so   you   could   potentially   handle   a   bigger,   a   bigger   K   this   way.   I   mean,   okay,   again,   you   still   have   to   do   the   merge.   But   for   um   for   GPUs,   you   have   a   lot   more   threads.   And   so   you   you   this   only   m   makes   sense   for   a   much   smaller   k.
      </p>

        <cite>Conor</cite>
      <time>22:32</time>
      <p>
          Yeah.
      </p>

        <cite>Bryce</cite>
      <time>22:33</time>
      <p>
          What&#39;s   the   complexity   of   uh   of   pushing   into   like   a   priority?
      </p>

        <cite>Conor</cite>
      <time>22:37</time>
      <p>
          It&#39;s   log   n,   log   n   where   n   is   the   length   of   the   the   q.
      </p>

        <cite>Bryce</cite>
      <time>22:41</time>
      <p>
          Right.   Or   n   is   the   length   of   the   q.
      </p>

        <cite>Conor</cite>
      <time>22:43</time>
      <p>
          Yeah.   I   always   it   always   irritated   me   back   when   I   was   in   my   interviewing   days   when   you&#39;d   have   some   quadratic   complexity   question,   and   then   you&#39;d   say   where   they&#39;d   say   what&#39;s   the   time   complexity,   and   then   you&#39;d   say,   ah,   it&#39;s   quadratic.   But   technically,   like   the   n   the   two   n&#39;s   that   you&#39;re   multiplying   are   not   actually   the   same.   It&#39;s   like   n   by   m.   So   the   complexity   is   not   quadratic,   it&#39;s   n   times   m.   I   always   thought   that   was   just   I   mean,   technically,   n   times   m   is   correct,   but   you   know,   at   a   high   level,   it&#39;s   quadratic,   you   know.   You   got   the   you   got   a   rectangle   of   data,   it&#39;s   quadratic.   But   then   they&#39;d   always   they&#39;d   always   be   like,   oh,   it&#39;s   not   quadratic,   and   I&#39;d   be   like,   I   mean,   technically   it&#39;s   n   by   m,   but   like   let&#39;s   move   on   to   the   next   question,   folks.
      </p>

        <cite>Bryce</cite>
      <time>23:28</time>
      <p>
          Uh   no,   you   know   what?   I   I   think   I   miss   I   think   I   misspoke   before.   I   think   that   this   does   maybe   pay   off.   Because   merge   sort   is   n   log   n,   which   is   worse   than   n.   Yes?
      </p>

        <cite>Conor</cite>
      <time>23:38</time>
      <p>
          Yes,   definitely.
      </p>

        <cite>Bryce</cite>
      <time>23:40</time>
      <p>
          I   think   I   said,   I   think   I   mistakenly   said   earlier   that   it&#39;s   not.   So   I   think   you   can   get   to   well,   no,   okay,   alright,   no.   Because   because   think   about   it,   if   if   what   you   have   to   do   for   every   element   is   that   you   have   to   push   heap.   Well,   no,   actually,   maybe   not.   Okay.   So   so   if   you   for   every   element,   if   you   have   to   push   into   a   k-sized   heap,   then   you&#39;re   doing   a   log   k   operation   for   n   elements,   right?   Which   is   better   than   n   log   n.   And   then   the   only   other   cost   that   you   have   is   the   cost   of   doing   the   merge.
      </p>

        <cite>Conor</cite>
      <time>24:15</time>
      <p>
          Yes.   Uh   and   also,   too,   like   technically   the   time   complexity   is   n   log   k,   but   you&#39;re   not   always   going   to   be   doing   the   insertion.   Like   the   time   complexity   is   the   worst   case,   but   like   on   average,   you&#39;re   probably   only   going   to   be   doing   the   log   k   insertion,   I   don&#39;t   know,   like   a   percentage   of   the   time.   Is   it   half?   Is   it   20%?   Is   it   10?   We   don&#39;t   know.   It   depends   on   the   data.   In   the   worst   case,   you&#39;ll   have   to   do   it   every   time   in   some   like   whatever   reverse   sorted   or   sorted   sequence.   But   in   the   average   case,   you&#39;re   going   to   do   some   check   to   see   is,   you   know,   when   you   if   before   you   do   the   insertion,   I   think   I   think   maybe   when   you   actually   push   into   it.   I   don&#39;t   know   if   that   how   that   actually   works.   So   like   it   might   already   take   care   of   it   when   you   try   to   insert   into   a   min   heap   and   it&#39;s   gr   it&#39;s   greater   than   the   largest   value   or   whatever,   it   uh   it&#39;ll   just   discard   it,   and   that&#39;s   like   an   O1   operation,   right?   So   it&#39;s   really   it&#39;s   really   gonna   be   better   than   like   N   log   K.
      </p>

        <cite>Bryce</cite>
      <time>25:10</time>
      <p>
          It&#39;s   gonna   be   and   we   might   be   able   to   kind   of   ignore   the   cost   of   the   merges   of   having   to   merge   these   heaps   together.   And   the   reason   I   say   that   is   because   the   order   of   magnitude   of   like   uh   uh   how   many   merge   like   uh   the   order   of   magnitude   of   the   elements   involved   in   the   merges   is   much   smaller   than   the   order   of   magnitude   of   the   inputs   here.
      </p>

        <cite>Conor</cite>
      <time>25:35</time>
      <p>
          So   they&#39;re   kind   of   MRT.
      </p>

        <cite>Bryce</cite>
      <time>25:37</time>
      <p>
          Yeah,   we&#39;re   assuming   in   this   problem   that   the   order   of   magnitude   of   K   is   substantially   smaller   than   N.   And   we&#39;re   also   assuming   in   this   problem   that   the   order   of   magnitude   of   the   number   of   parallel   execution   agents   is   substantially   smaller   than   um   uh   than   n.   So   like   even   on   a   GPU,   like   let&#39;s,   you   know,   you   might   have   you   know   uh   thousands   or   or   hundreds   of   thousands   of   threads,   but   I   think   that   you   would   only   need   on   a   GPU   to   have   one   of   these   heaps   per   um   thread   block.   Uh   and   GPU&#39;s   thread   blocks   are   gonna   be   in   the   thousands.
      </p>

        <cite>Conor</cite>
      <time>26:18</time>
      <p>
          Yeah.
      </p>

        <cite>Bryce</cite>
      <time>26:19</time>
      <p>
          Um   and   you   would   have   you   know   at   least   millions,   but   probably   tens   of   millions   or   hundreds   of   millions   of   input   elements.   Um   and   so   the   merge   costs   may   not   you   know   be   that   expensive.
      </p>

        <cite>Conor</cite>
      <time>26:30</time>
      <p>
          Yeah.
      </p>

        <cite>Bryce</cite>
      <time>26:31</time>
      <p>
          Huh.
      </p>

        <cite>Conor</cite>
      <time>26:32</time>
      <p>
          All   right.   Well,   we&#39;re   at   the   halfway   mark   of   the   recording.   Do   we   want   to   do   we   want   to   wrap   up   this   topic?   Any   final   thoughts   on   the   top   K,   parallel   top   K?
      </p>

        <cite>Bryce</cite>
      <time>26:40</time>
      <p>
          Well,   Elias,   if   you&#39;re   listening,   you   should   go   prototype   this.
      </p>

        <cite>Conor</cite>
      <time>26:43</time>
      <p>
          Perfect.   Delegating   work.   All   right.   That&#39;s   episode   187,   if   I&#39;ve   got   my   numbering   correct.   Be   sure   to   check   these   show   notes   either   in   your   podcast   app   or   at   adsphepodcast.com   for   links   to   anything   we   mentioned   in   today&#39;s   episode,   as   well   as   a   link   to   a   GitHub   discussion   where   you   can   leave   thoughts,   comments,   and   questions.   Thanks   for   listening.   We   hope   you   enjoyed   and   have   a   great   day.
      </p>

        <cite>Bryce</cite>
      <time>27:04</time>
      <p>
          Low   quality,   high   quality,   that   is   the   tagline   of   our   podcast.
      </p>

        <cite>Conor</cite>
      <time>27:09</time>
      <p>
          That&#39;s   not   the   tagline.   Our   tagline   is   chaos   with   sprinkles   of   information.
      </p>