

        <cite>Conor</cite>
      <time>0:00</time>
      <p>
          Ben,   we&#39;re   talking   about   Ben.   Prolific   speaker   on   the   C   speaker   track,   uh,   algorithm   expert,   polyglot.
      </p>

        <cite>Ben Deane</cite>
      <time>0:07</time>
      <p>
          Entendlement   is   interesting   for   another   reason.   It&#39;s   I&#39;ve   long   considered   it   the   sort   of   most   unloved   algorithm   or   most   overlooked   algorithm.
      </p>

        <cite>Conor</cite>
      <time>0:26</time>
      <p>
          Welcome   to   ADSP   the   podcast   episode   75,   recorded   on   April   19th,   2022.   My   name   is   Connor,   and   today   with   my   co-host   Bryce,   we   talk   to   algorithm   expert   Bendine   about   C   algorithms.   Well,   let&#39;s   let&#39;s   do   this   right   off   the   bat.
      </p>

        <cite>Bryce</cite>
      <time>0:44</time>
      <p>
          We&#39;re   hopping   we&#39;ll   well   before   we   hop   into   things,   we&#39;ll   get   uh   I   I   know   I   have   a   feeling   I   know   what   Connor&#39;s   about   to   do.   They&#39;re   never   gonna   sponsor   us,   Connor.   They&#39;re   never   gonna   sponsor   us.   Did   you   hear   net   Netflix   down   20%   to   the   after   after   hours   today?   So   maybe   maybe   maybe   NVIDIA   will   replace   Netflix   as   the   N   in   uh   uh   in   Fang.
      </p>

        <cite>Ben Deane</cite>
      <time>1:10</time>
      <p>
          I   feel   like   that   acronym   is   now   increasingly   irrelevant   with   the   players   in   the   market,   you   know.
      </p>

        <cite>Bryce</cite>
      <time>1:17</time>
      <p>
          I   feel   like   I   throw   a   lot   of   shade   at   Netflix   on   this   podcast   for   absolutely   no   reason.   And   if   anybody   who   works   at   Netflix   is   listening   to   this   podcast,   I   really   have   no   problem   with   you.   It   sounds   like   a   great   company,   but   I   will   continue   to   throw   shade.   Alright,   Connor,   do   your   thing.
      </p>

        <cite>Conor</cite>
      <time>1:36</time>
      <p>
          Um,   our   thing   is   that   we&#39;re   terrible.   Well,   we&#39;re   good.   I   think   we&#39;re   decent   podcast   co-hosts,   uh,   but   we   do   a   terrible   job   of   introducing   our   guests   as   as   demonstrated   by   our   last   recording   with   guests   when   we   had   Patrice   and   uh   Jason.
      </p>

        <cite>Bryce</cite>
      <time>1:49</time>
      <p>
          I   thought   this   was   a   bubbly.   I   thought   you   were   gonna   go   do   a   bubbly.
      </p>

        <cite>Conor</cite>
      <time>1:52</time>
      <p>
          Oh   no,   we   well,   we&#39;ve   got   the   brand   new   bubbly   flavor.
      </p>

        <cite>Ben Deane</cite>
      <time>1:55</time>
      <p>
          It&#39;s   well,   so   how   is   bubbly?   Because   uh   what&#39;s   the   name   of   the   other   one?   I   can&#39;t   remember.   Um   uh   Perrier?   No,   no.   Uh-huh.   No.
      </p>

        <cite>Bryce</cite>
      <time>2:08</time>
      <p>
          They   even   they   spell   bubbly   wrong.
      </p>

        <cite>Ben Deane</cite>
      <time>2:11</time>
      <p>
          Oh   gosh.   I   had   one   today   and   I   can&#39;t   even   remember   the   one.   No,   it&#39;s   uh   it&#39;s   a   flavored,   it&#39;s   it&#39;s   Le   Croix?   La   Croix,   that&#39;s   the   one.   Oh   see,   that&#39;s   big   down   in   the   States.   It&#39;s   not   really   that   big   up   here   in   Canada.   But   I&#39;ve   just   discovered   Spindrift,   which   is   which   is   like   La   Croix,   but   nice.   It&#39;s   I   have   to   say   they   have   compromised.   It&#39;s   not   zero   calories,   it&#39;s   a   whole   five   calories   a   can.
      </p>

        <cite>Bryce</cite>
      <time>2:35</time>
      <p>
          La   Croix,   if   you   want,   if   you   want   to   sponsor   us,   we   will   make   Ben   come   back   and   apologize.
      </p>

        <cite>Ben Deane</cite>
      <time>2:40</time>
      <p>
          I&#39;m   not   a   big   LaCroix   drinker,   but   I   do   drink   LaCroix,   but   I&#39;ve   recently   discovered   Spindrift.
      </p>

        <cite>Bryce</cite>
      <time>2:44</time>
      <p>
          We   tolerate   it.   We   tolerate   everything.
      </p>

        <cite>Conor</cite>
      <time>2:47</time>
      <p>
          Yeah,   exactly.   What&#39;s   what&#39;s   the   difference?   See,   well,   I   just   want   to   talk   like   this   is   meta   because   we   were   gonna   this   is   what   we&#39;re   we   are   literally   proving   what   we&#39;re   bad   at.   We&#39;re   bad   at   introducing   our   guests.   We   got   two   seconds   into   introducing   Ben,   and   then   Bryce   was   like,   weren&#39;t   you   gonna   talk   about   bubbly?   And   then   whatever   percentage   of   like   attention   deficit   disorder   I   have,   I   was   like,   no,   but   let   me   tell   you,   and   now   we&#39;re   talking,   anyways,   let&#39;s   finish   this   topic.   Uh   Spindrift,   is   that   what   it&#39;s   called?   Spindrift?
      </p>

        <cite>Ben Deane</cite>
      <time>3:12</time>
      <p>
          Spindrift   is   is   like   LeCroix,   except   they&#39;ve   compromised,   as   I   say,   very,   very   slightly   on   the   calories   for   much   nicer   flavor,   in   my   opinion.   Interesting.
      </p>

        <cite>Bryce</cite>
      <time>3:23</time>
      <p>
          You   know,   my   my   my   go-to   drink   is   vitamin   Water   Zero.   I   literally   have   a   fridge   full   of   vitamin   Water   Zero   at   all   times.
      </p>

        <cite>Conor</cite>
      <time>3:31</time>
      <p>
          I   like   I   don&#39;t   drink   water.   I   just   isn&#39;t   that   like   the   crypto,   isn&#39;t   that   like   the   crypto   of   drinks?   It&#39;s   just   a   big   scam.
      </p>

        <cite>Bryce</cite>
      <time>3:38</time>
      <p>
          It&#39;s   I&#39;m   uh   it   tastes   too   good   to   have   zero   calories.   I&#39;m   sure   something   in   it   is   gonna   kill   me,   but   I   am   addicted.
      </p>

        <cite>Conor</cite>
      <time>3:46</time>
      <p>
          That&#39;s   fair   enough.
      </p>

        <cite>Bryce</cite>
      <time>3:47</time>
      <p>
          Literal,   literally,   my   my   my   mother   was   here   the   last   week   visiting   me,   and   she&#39;s   like,   I   want   a   glass   of   water.   There&#39;s   no   water   in   this   apartment.   Can   I   just   have   some   regular   water?
      </p>

        <cite>Conor</cite>
      <time>3:57</time>
      <p>
          Wait,   don&#39;t   you   isn&#39;t   is   the   tap   water   in   New   York   not   drinkable?
      </p>

        <cite>Bryce</cite>
      <time>4:01</time>
      <p>
          It   is,   but   I   don&#39;t   know.   Like   they   want   all   of   all   of   the   women   in   my   life   want   like   old   water,   and   my   apartment   does   not   have   it.
      </p>

        <cite>Conor</cite>
      <time>4:11</time>
      <p>
          Alright.   Well,   any   of   the   companies,   uh,   aforementioned   companies,   including   Sapsucker,   which   might   be   the   spindrift   of   Canada,   which   I   think   it   has   like   20   calories   or   15   calories   a   can,   but   it&#39;s   like   it   takes   like   recycled,   I   don&#39;t   know,   syrup   or   something.
      </p>

        <cite>Bryce</cite>
      <time>4:28</time>
      <p>
          And   um   recycled?
      </p>

        <cite>Conor</cite>
      <time>4:30</time>
      <p>
          I   don&#39;t   know.   Honestly,   it&#39;s   got   it&#39;s   something   it   comes   something   from   a   tree.   Something   from   a   tree&#39;s   in   it.
      </p>

        <cite>Bryce</cite>
      <time>4:37</time>
      <p>
          I   don&#39;t   want   syrup   that   somebody   else   has   already   had.
      </p>

        <cite>Conor</cite>
      <time>4:40</time>
      <p>
          I   I   don&#39;t   think   that&#39;s   I   don&#39;t   think   that&#39;s   what   it   is,   but   it&#39;s   like   I   think   there&#39;s   a   process   of   making   syrup,   and   then   there&#39;s   some   like   uh,   you   know,   like   in   an   oil,   what   do   they   call   that   stuff   in   an   oil   plant   or   oil   refinery,   and   then   there&#39;s   like   a   pool   where   all   the   bad   stuff   goes.   It&#39;s   called   like   something   off.
      </p>

        <cite>Bryce</cite>
      <time>4:56</time>
      <p>
          Oh,   that   makes   more   sense.   That   makes   more   sense.   What   did   you   I   think   Ben   actually   knew   the   name   of   it?
      </p>

        <cite>Ben Deane</cite>
      <time>5:00</time>
      <p>
          What   is   it   called?   You   mean   like   a   sump?   Like   that   just   collects   the   runoff   kind   of   yeah,   yeah,   runoff.
      </p>

        <cite>Conor</cite>
      <time>5:06</time>
      <p>
          That&#39;s   what   I   was   thinking   of.   That&#39;s   the   word.   Um   my   older   sister   as   an   engineer   would   have   definitely   uh   had   it   right   away.   And   uh   sister?   Shannon.   She&#39;s   um   yeah,   she&#39;s   in   Calgar   now.   Left   left   me   all   alone   in   Toronto,   but   uh   I   think   it&#39;s   basically   the   runoff   of   like   maple   syrup,   which   is   still   good   for   stuff,   but   not   syrup.   And   so   this   drink   company   could   be   the   spindriff   equivalent.
      </p>

        <cite>Ben Deane</cite>
      <time>5:30</time>
      <p>
          Speaking   of   syrup,   I   was   gonna   say   the   current   syrup   I   have   in   my   fridge.   I   just   made   pancakes   and   I   noticed   on   the   bottle,   and   this   is   gonna   offend   everyone,   right?   On   the   bottle   it   says   product   of   USA   and   Canada.
      </p>

        <cite>Bryce</cite>
      <time>5:42</time>
      <p>
          Oh,   that   is   that   is   wrong.   That   is   wrong.   Why?   There   is   one   good   maple   tree   product   from   Canada,   and   that&#39;s   maple   butter,   specifically   the   type   of   maple   butter   that   JF&#39;s   brother   brings   me   every   time   I   see   him.   And   yes,   this   is   a   coded   way   of   me   telling   JF   to   tell   his   brother   to   continue   to   bring   me   uh   maple   butter.
      </p>

        <cite>Conor</cite>
      <time>6:09</time>
      <p>
          He   just   said   like   two   episodes   ago   that   he   doesn&#39;t   have   time   to   listen   to   this.   You   just   ripped   on   him   for   like   10   minutes.
      </p>

        <cite>Bryce</cite>
      <time>6:14</time>
      <p>
          Somebody   else   will   listen   to   this,   like   honor   somebody,   and   and   will   then   tell   JF,   and   then   JF   will   tell   his   brother,   I   got   a   system.   But   no,   real   maple   syrup   is   uh   is   made   in   Vermont.   It   is   it   is   a   product   of   Vermont,   America.
      </p>

        <cite>Conor</cite>
      <time>6:29</time>
      <p>
          Alright,   ten   minutes   later.   Today,   our   guest,   I   think,   other   than   Sean   Parent,   you   are   the   second   ever   returning   guest   to   the   podcast,   unless   if   my   memory&#39;s   failing   me.   We&#39;ve   definitely   and   and   for   the   listener,   we   cut   every   time   we   record   with   someone   into   like   two   or   three   episodes.   So   if   you&#39;re   thinking,   what   are   you   talking   about?   Everyone&#39;s   been   on   two   or   three   times.   False,   everyone&#39;s   been   on   once,   except   for   Sean   Parent,   and   then   we   we   cut   that   up   into   30   to   35,   40   minute   episodes.   So,   Ben,   the   last   time   you   were   on   was   in   um   the   on   during   the   virtual   C   Now   of   2020,   I   think.
      </p>

        <cite>Bryce</cite>
      <time>7:04</time>
      <p>
          No,   it   was   2021.
      </p>

        <cite>Ben Deane</cite>
      <time>7:06</time>
      <p>
          I   was   gonna   say   this   almost   this   time   last   year.
      </p>

        <cite>Bryce</cite>
      <time>7:08</time>
      <p>
          This   podcast   did   not   exist   at   the   time   of   that   where   C   now   2020   would   have   happened.
      </p>

        <cite>Ben Deane</cite>
      <time>7:15</time>
      <p>
          You&#39;re   on   your   74th   week   or   whatever   it   is.
      </p>

        <cite>Conor</cite>
      <time>7:18</time>
      <p>
          Yeah,   let&#39;s   well,   let&#39;s   be   honest.   We&#39;ve   all   lost   track   of   time   and   uh   in   in   this   virtual   new   world   that   we   live   in.   Um   but   wait,   Bryce,   don&#39;t   say   anything.   We   were   we   were   like   we   were   we   were   almost   there,   we   were   almost   introducing   him.   Uh   hands   are   on   the   hills.   So   if   you   if   you&#39;re   in   the   C   community,   you&#39;ve   probably   heard   of   Ben.   Uh   he&#39;s   a   prolific   talk   speaker,   winner   of   many   best   speaker   awards   at   C   now.
      </p>

        <cite>Bryce</cite>
      <time>7:40</time>
      <p>
          Did   you   say   talk   speaker?
      </p>

        <cite>Conor</cite>
      <time>7:42</time>
      <p>
          I&#39;m   a   talk   speaker.   Well,   you   know,   honestly,   folks,   I   should   read   a   sentence   that   I   wrote   the   other   day   on   Discord.   It   was   so   there   were   so   many   skipped   words   and   grammar   mistakes.   Anyways,   so   he&#39;s   a   prolific   speaker   with   dude.
      </p>

        <cite>Ben Deane</cite>
      <time>7:58</time>
      <p>
          Speaker   with   you.
      </p>

        <cite>Conor</cite>
      <time>8:00</time>
      <p>
          Speaker,   I   think   that&#39;s   the   one   too   proper.   I   gotta   be   honest,   I   just   got   back   from   running   18k   uh   very   quickly   at   Run   Club.   So   I&#39;m   a   little   bit   in   uh   I&#39;ve   like   I&#39;m   in   like   a   two   and   a   half   thousand   calorie   deficit   right   now.
      </p>

        <cite>Bryce</cite>
      <time>8:14</time>
      <p>
          Did   you   shower?
      </p>

        <cite>Conor</cite>
      <time>8:15</time>
      <p>
          I   did,   yeah.   Uh   and   I   I   showered   right   before.   Anyways,   Ben,   we&#39;re   talking   about   Ben,   prolific   speaker   on   the   C   speaker   track,   uh,   algorithm   expert,   polyglot.   If   you&#39;ve   listened   to   his   CPP   cast   episode,   I   think   you   started   off   by   talk   going   through   the   uh   plethora   of   languages   that   you   have   um   studied   at   one   point   or   used.   Um   likely.
      </p>

        <cite>Ben Deane</cite>
      <time>8:37</time>
      <p>
          Jason   always   asks   about   history   and   that   sort   of   thing.   So   yeah.
      </p>

        <cite>Conor</cite>
      <time>8:41</time>
      <p>
          Yes,   a   fellow   uh   Ben   is   a   fellow   uh   program   language   historian   uh   enthusiast.   What   do   you   what   is   it?   Is   it   a   bookophile   or   uh   some   someone   you   have   a   library?   Bibliophile?   Bibliophile.
      </p>

        <cite>Bryce</cite>
      <time>8:53</time>
      <p>
          You   are   really   bad   at   words   today,   Connor.
      </p>

        <cite>Conor</cite>
      <time>8:56</time>
      <p>
          This   is   gonna   be   a   rough   takeoff.   And   the   reason   Ben&#39;s   on   today,   and   Ben&#39;s   one   of   my   favorite   speakers,   what   let&#39;s   list   off   a   couple   of   your   talks.   What&#39;s   the   I&#39;m   not   even   gonna   remember   any   of   the   names   of   them.   Declarative.
      </p>

        <cite>Ben Deane</cite>
      <time>9:06</time>
      <p>
          Yeah.   One   was   called   easy   to   use,   hard   to   misuse,   declarative   style   in   C.   Yes.   Fantastic.
      </p>

        <cite>Bryce</cite>
      <time>9:13</time>
      <p>
          Ben,   what&#39;s   your   favorite   talk   that   you&#39;ve   ever   given?   Uh   that&#39;s   probably   a   hard   question   to   answer.
      </p>

        <cite>Ben Deane</cite>
      <time>9:18</time>
      <p>
          That&#39;s   a   hard   one,   but   I   suspect   like   several   speakers,   I   feel   like   I&#39;ve   given   the   same   talk   in   different   guises   several   times.   Um,   or   variations   on   a   theme.   There   are   two   styles   of   talks   that   I   really   think   about.   The   easy   style,   which   is   here&#39;s   a   thing   I   did,   here&#39;s   the   code,   here&#39;s   a   C   feature,   here&#39;s   how   to   explain   here&#39;s   how   to   think   about   it,   explain   it,   etc.   Right?   The   easy   style   of   talk   to   me   is   like   you   have   code,   you   explain   it.   The   harder   style,   the   more   but   the   more   rewarding   style   is   the   sort   of   more   philosophical   style.   Um   can   be   illustrated   with   code,   of   course,   but   uh   that   style   is   more   of   the   kind   of   declarative   style   talk.   So   I   like   I   like   both   styles.   Like   I   I   I   like   the   philosophical   style,   but   but   the   easier   one   to   put   together   is   definitely   like   here&#39;s   the   code,   here&#39;s   how   it   works   style.   Easy   to   use,   yeah.
      </p>

        <cite>Conor</cite>
      <time>10:10</time>
      <p>
          Easy   to   use,   hard   to   misuse.   You   had   the   other   one   too   recently,   I   think   it   was   at   CPPCon,   which   was   the   or   no,   that   was   at   C   now   as   well.   Identifying   monoids.   Is   that   yeah?   And   also   the   talk   that   uh   I   don&#39;t   think   ever   gets   mentioned   enough.   And   it   definitely,   well,   it   was   at   CPPCon,   so   it   didn&#39;t   quote   unquote   win   any   awards,   which   is   maybe   why   some   of   the   other   ones   get   more   buzz,   uh,   even   though   obviously   they&#39;re   they&#39;re   really   good,   is   the   std   accumulate   and   algorithm   empire.   I   think   that   talk   is   fantastic   because   of   sort   of   just   the   exercise   of,   I   think   you   use   the   word   sort   of   perversely,   like   you&#39;re   using   the   algorithms   in   ways   they   shouldn&#39;t   be   used.   Yes.   And   and   bending   them   as   an   exercise   to   really   see   like   what   they&#39;re   capable   of.   And   a   bunch   of   the   things   you   point   out   is   like,   don&#39;t   do   this   stuff,   but   the   exercise   of   doing   this   with   the,   you   know,   where   you   give   a   little   summary   of   the   talk.
      </p>

        <cite>Ben Deane</cite>
      <time>11:00</time>
      <p>
          Well,   that   talk,   like   the   talk   that   Jason   and   I   did,   constexpr   things,   it   it&#39;s   kind   of   interesting   to   look   back   and   see   that   that   talk   is   of   its   time,   right?   And   to   look   back   and   be   like,   wow,   that   was   like   you   say,   that   was   just   an   exercise   in   making   accumulate   implement   different   algorithms,   and   it   was   a   sort   of   a   thought   experiment,   if   you   like.   I   mean,   it   was   an   actual   code   experiment,   but   in   a   sense   it&#39;s   a   thought   experiment,   but   interesting,   but   interesting   to   look   back   at   and   see,   you   know,   it&#39;s   kind   of   of   its   time   now,   and   I   look   like   all   of   us,   I   look   back   at   my   own   code   and   I   think,   you   know,   what   was   I   thinking?   I   shouldn&#39;t   have   done   that.   Like   there   are   better   ways   to   do   that.   In   a   sense,   for   that   talk,   it&#39;s   fine   because   the   whole   thing   is   predicated   on   just   this   is   really   interesting   and   a   good   way   to   think   about   it,   but   don&#39;t   ever   write   this   code   sort   of   thing.
      </p>

        <cite>Conor</cite>
      <time>11:49</time>
      <p>
          The   key   quote   from   that   talk   that   I&#39;ve   sort   of   clipped   into   a   couple   of   my   talks   is   that   at   a   certain   point   you   go   through   the   exercise   of   seeing   how   many   algorithms   you   can   actually   implement   using   std   accumulate   or   some.   The   sort   of   platonic   equivalent   of   std   accumulate,   yeah.   Yeah.   And   yes,   so   77   of   the   90   of   the   Right,   right.
      </p>

        <cite>Ben Deane</cite>
      <time>12:08</time>
      <p>
          In   I   think   we   had   90   algorithms   in   14,   something   like   that.
      </p>

        <cite>Bryce</cite>
      <time>12:12</time>
      <p>
          Connor,   what   just   like   one   sec,   one   sec.   Connor   is   experiencing   undefined   behavior   right   now.
      </p>

        <cite>Ben Deane</cite>
      <time>12:22</time>
      <p>
          Yes.   Come   back   to   us,   Connor.   Are   you   good?   Can   people   can   people   hear   me?   Yeah.
      </p>

        <cite>Bryce</cite>
      <time>12:26</time>
      <p>
          We   can   hear   you   throughout   the   entire   ordeal.
      </p>

        <cite>Ben Deane</cite>
      <time>12:29</time>
      <p>
          I&#39;m   guessing   the   listener   can   also   hear   you.
      </p>

        <cite>Conor</cite>
      <time>12:32</time>
      <p>
          I   in   the   middle   of   me   saying   the   77   of   the   90   algorithms   are   implementable   in   terms   of   accumulate.   Uh,   this   woman   started   talking   in   my   headphones   saying,   Your   headphones   are   out   of   battery.   Please   recharge,   turning   off.   Okay.
      </p>

        <cite>Bryce</cite>
      <time>12:50</time>
      <p>
          See,   but   I   feel   I   feel   like   that   was   probably   not   the   first   warning   that   you   got   that   your   headphones   were   low   on   battery   because   that&#39;s   true.
      </p>

        <cite>Conor</cite>
      <time>12:56</time>
      <p>
          That&#39;s   true.   That   lady   said   something   earlier   today,   and   I   ignored   her.
      </p>

        <cite>Bryce</cite>
      <time>13:00</time>
      <p>
          Um   Yeah,   you   should   have   listened.
      </p>

        <cite>Conor</cite>
      <time>13:01</time>
      <p>
          Alright,   Ben,   back   to   you.
      </p>

        <cite>Ben Deane</cite>
      <time>13:02</time>
      <p>
          You   were   gonna   say   one   of   your   talks.   One   of   my   talks   that   had   quite   a   bit   of   impact   and   people   still   seem   to   remember   uh   or   or   at   least   let&#39;s   say   folks   outside   of   the   rarefied   bubble   of   conference   speakers   that   I   talk   to   sort   of   in   the   real   world   uh   and   or   in   the   games   industry   as   I   was   in,   um   they   really   enjoyed   the   um   using   types   effectively   talk   that   I   gave   uh   to   I   think   it   was   CPPCon   16.   Is   that   the   one   where   you   have   the   you   know   how   many   types   of   I   have   a   little   game,   yeah,   a   little   type   theory   game   um   talking   about   sites   ty   uh   types   as   characterized   by   the   cardinality   of   the   set   of   values   they   hold.
      </p>

        <cite>Bryce</cite>
      <time>13:43</time>
      <p>
          Are   you   are   you   coming   to   C   Post   Post   now   this   year,   Ben?
      </p>

        <cite>Ben Deane</cite>
      <time>13:46</time>
      <p>
          Yep.   Yes,   I&#39;ll   be   there.   That&#39;s   in   just   over   that&#39;s   in   less   than   two   weeks   now,   right?
      </p>

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

        <cite>Conor</cite>
      <time>13:51</time>
      <p>
          Yeah,   by   the   time   this   airs,   what   day   is   it?   It&#39;s   the   19th   century.
      </p>

        <cite>Bryce</cite>
      <time>13:56</time>
      <p>
          In   fact,   one   of   the   reasons   that   we&#39;re   recording   this   is   because   I   will   be   at   C   Post   Post   now.   And   uh   or   the   one   of   the   reasons   we&#39;re   recording   this   now   is   because   I&#39;m   gonna   be   gone   for   the   first   two   weeks   of   May.   And   uh   and   Connor   needs   all   the   Bryce   Gold   to   produce   to   produce   the   podcast.
      </p>

        <cite>Conor</cite>
      <time>14:14</time>
      <p>
          Maybe   I&#39;ll   just   end   up   going   solo.
      </p>

        <cite>Bryce</cite>
      <time>14:17</time>
      <p>
          We&#39;ve   never   we&#39;ve   never   done   an   episode   where   we   No   no   no   that&#39;s   not   true.   We   had   the   one   episode,   right?   At   C   Plus   P   now   last   year.   One   episode   without   me.
      </p>

        <cite>Ben Deane</cite>
      <time>14:27</time>
      <p>
          Connor   and   Tony   and   I.
      </p>

        <cite>Conor</cite>
      <time>14:29</time>
      <p>
          Yeah.   Ben   it   was   Ben   and   I   for   the   first   bit,   and   then   Canadians   have   a   habit   of   showing   up   halfway   into   the   recordings.
      </p>

        <cite>Bryce</cite>
      <time>14:36</time>
      <p>
          Um   that&#39;s   not   foreshadowing.   There&#39;s   no   random   Canadian   showing   up   today.
      </p>

        <cite>Ben Deane</cite>
      <time>14:42</time>
      <p>
          So   how   this   goes   is   I   I   listen   to   your   your   podcast   probably   every   other   week.   Um,   and   I   catch   up.   And   then   invariably,   it&#39;s   like   on   the   Saturday   morning   when   I   have   some   time,   and   then   invariably   I   I   I   DM   Connor   on   Twitter.   I   only   use   Twitter   for   DMs   these   days,   but   I   DM   Connor   and   I   say,   I   have   opinions.
      </p>

        <cite>Conor</cite>
      <time>15:02</time>
      <p>
          This   is   true.   And   this   is   why   Ben,   so   Ben,   this   so   this   is   uh   gonna   be,   I   think,   I&#39;m   not   sure   if   it&#39;s   a   response   to   multiple   podcasts,   but   Ben   DM&#39;d   me   after   the   C   algorithm   family   feud   interview   question.   Uh   of   which,   oh,   I   should   I   should   call   out.
      </p>

        <cite>Bryce</cite>
      <time>15:18</time>
      <p>
          We&#39;ve   got   we&#39;ve   had   like   two   or   three   people   who   have   coded   up   the   solution.
      </p>

        <cite>Conor</cite>
      <time>15:22</time>
      <p>
          Two   people,   one   of   them   was   from   the   C   well,   shout   out   to   the   C   North   Denver   meetup,   because   I   believe   Tyler   Oh   right.   What   was   it?   I   want   to   get   the   name   correct   here.   Tyler   Weaver   made   both   a   YouTube   video   and   sort   of   a   God   bolt   and   a   quick   bench,   and   was   basically   saying   that   it   looked   like   the   max   element   where   removing   an   element   and   then   just   doing   another   max   element   was   the   fastest   and   transform   reduce   was   like   the   slowest.
      </p>

        <cite>Bryce</cite>
      <time>15:50</time>
      <p>
          I   wasn&#39;t   that   ridiculous   max   element   thing   my   idea.
      </p>

        <cite>Conor</cite>
      <time>15:54</time>
      <p>
          Yeah,   but   we   said   it   was   a   bad   idea,   though.
      </p>

        <cite>Bryce</cite>
      <time>15:56</time>
      <p>
          Hey,   hey,   hey,   hey.   I,   sir,   I   sir   am   an   architect   now.   My   job   is   not   is   not   to   write   code   or   to   have   good   ideas.   My   idea   my   job   is   just   to   come   up   with   ideas,   and   somebody   else   figures   out   if   they&#39;re   good   or   not.
      </p>

        <cite>Conor</cite>
      <time>16:13</time>
      <p>
          It&#39;s   it&#39;s   yeah.   Well,   so   we&#39;ll   get   back   to   this.   But   anyways,   there   were   Tyler   Weaver   had   a   YouTube   video,   and   uh   there   was   another   individual.   I&#39;ll   grab   his   name   at   some   point.   But   so   Ben   DM&#39;d   me   after   listening   to   this   and   said,   We   need   to   chat.   And   I   said,   uh,   do   you   want   to   come   on   the   podcast?   And   he   said,   Yeah,   sure,   it   doesn&#39;t   matter   to   me   as   long   as   we   get   the   chat.
      </p>

        <cite>Bryce</cite>
      <time>16:31</time>
      <p>
          And   so   we   need   to   have   we   need   to   talk,   we   need   to   have   conversation.
      </p>

        <cite>Conor</cite>
      <time>16:35</time>
      <p>
          Well,   this   is   it.   Like,   I   have   opinions,   right?   Yeah,   who   who   is   it   that   messed   up   the   worst?   Was   it   me   or   was   it   Bryce?
      </p>

        <cite>Ben Deane</cite>
      <time>16:42</time>
      <p>
          No   one   messed   up.   And   and   I   actually   really   enjoyed   the   format   where   like   the   game   show   format   where   you&#39;re   like   you&#39;re   like,   okay,   Bryce,   now   name   name   the   answer.   Oh,   but   name   the   series   of   answers   in   reverse   order.   So   when   you   posed   the   question,   which   was   uh   find   the   top   two,   right? Or   the   or   the   minimum   two   or   the   maximum   two,   same   same   thing,   right?   In   an   unsorted   array   of   integers,   let&#39;s   say.   Um   my   immediate   thought   was   nth   element.   That&#39;s   what   nth   element   does.   That   like   and   and   then   uh   but   then   of   course,   as   is   your   won&#39;t,   um   you   solved   it   with   some   reduction.   And   that&#39;s   fine.   Of   course.
      </p>

        <cite>Bryce</cite>
      <time>17:25</time>
      <p>
          This   is   the   reduction.
      </p>

        <cite>Ben Deane</cite>
      <time>17:26</time>
      <p>
          Yeah,   yeah,   yeah,   yeah,   yeah.   So   so   it   kind   of   is.   I   still   believe   the   correct   name   for   that   algorithm   is   top   two   or   top   n,   but   perhaps.   I   mean,   I   I&#39;m   not   claiming   that   nth   element   is   particularly   a   good   name   for   that   application.   Uh   so   it   occurred   to   me   like   you   you&#39;re   interviewing   probably   for   library   developers,   right?   As   opposed   to   application   developers.   And   there&#39;s   a   difference   there.   That&#39;s   right.   Because   in   an   application   developer,   the   obvious   thing   is,   well,   nth   element,   right?   In   a   library   developer,   what   I   would   like   as   an   application   developer   is   for   nth   element   to   be   implemented   with   a   reduction   under   the   hood,   if   that   is   faster,   taking   into   account   array   size,   parallelism,   element   size,   that   sort   of   thing.   You   made   a   comment   to   that   effect   yourself,   Bryce,   where   you   said   something   about   like   the   the   you   know,   the   performance   may   vary   depending   on   several   of   those   things   anyway.
      </p>

        <cite>Bryce</cite>
      <time>18:24</time>
      <p>
          Yeah,   so   so   one   of   the   things   I   think   is   a   good   part   of   this   question,   and   if   if   I   I   you   know,   I   as   if   you   said   before,   I   don&#39;t   ask   technical   questions   in   interview   but   views.
      </p>

        <cite>Conor</cite>
      <time>18:35</time>
      <p>
          But   if   I   was   and   I   was   gonna   use   this   question,   um   look   at   Bryce,   trying   not   to   say   oh,   this   was   a   good   question.   Actually,   let   me   correct   myself.   It&#39;s   a   bad   it&#39;s   in   a   bad   category   of   questions   that   I   don&#39;t   endorse,   but   in   that   bad   category.
      </p>

        <cite>Bryce</cite>
      <time>18:50</time>
      <p>
          It&#39;s   more   I   call   into   question   the   entire   notion   of   how   like   traditional   tech   interviews   are   are   are   conducted.   But   that   aside,   um   if   I&#39;m   looking   for   a   library   developer,   I&#39;m   looking   for   somebody   who   looks   at   this   question,   comes   up   with   multiple   different   answers,   and   then   like   the   really   the   right   way   to   answer   this   question   is   to   tell   me   that   there   is   no   one   correct   answer.   That   here   are   the   options,   and   that   there   are   going   to   be   different   circumstances   under   which   these   will   be,   you   know,   each   one   of   these   will   be   the   right   one.   And   that   like   maybe   the   way   that   you   would   build   a   high   performance   implementation,   a   generic   implementation   of   this,   would   be   to   use   a   combination   of   different   strategies.
      </p>

        <cite>Ben Deane</cite>
      <time>19:36</time>
      <p>
          Yeah,   yeah.   Because   I   mean,   as   a   qu   as   a   very   specific   question,   top   two,   great.   The   generalization   is   top   n,   of   course,   which   in   some   sense   is   nth   element.   Yes.   And   and   that&#39;s   where   it&#39;s   like,   well,   top   two,   it,   you   know,   like   a   pair   is   very   easy,   a   very   small   amount   of   data,   assuming   you   have   a   small   element   size.   Um   but   if   you   want   top   a   thousand,   like   that   might   be   a   very   different   sort   of   problem   uh   that   that   parallelization   might   not   be   amenable   to.   And   in   general,   median   is   a   problem   that&#39;s   annoyingly   hard   to   parallelize,   I   think.
      </p>

        <cite>Conor</cite>
      <time>20:10</time>
      <p>
          It&#39;s   definitely   not   one   of   the   trivial   bread   and   butter,   like   a   reduction,   the   bread   and   butter   one.
      </p>

        <cite>Bryce</cite>
      <time>20:17</time>
      <p>
          Yeah.
      </p>

        <cite>Conor</cite>
      <time>20:17</time>
      <p>
          So   that&#39;s   interesting.   I   guess   my   first   thought   is   how   many   algorithms,   like   the   first   one   I   can   think   of   is   I   think   the   st   uh   std   sort   is   has   the   behavior   where   depending   on   the   size,   it   will   choose   different   uh   sort   algorithms.   And   I   think   like   the   actual   name   of,   I&#39;m   not   sure   if   it&#39;s   the   same   across   um   uh   libstdc   and   libclus   plus,   but   I   think   it   at   least   one   of   them   uses   intro   sort,   which   is   like   a   combination   of   merge   sort   and   I&#39;m   not   gonna   get   the   other   one   wrong,   but   like   quick   sort   or   something   like   that,   where   above   a   certain   size   it   chooses   merge   sort,   but   then   once   it   gets   down   below   a   certain   size,   it   then   switches   to   another   one,   and   that&#39;s   actually   um   there&#39;s   it&#39;s   something   similar   in   Python   that   they   have   some   kind   of   hybrid   algorithm   that&#39;s   and   it&#39;s   named   after   some   individual.   So   do   you   know   how   many   algorithms   actually   in   the   algorithm   header   have   behavior   like   that?   So   that&#39;s   basically   what   we&#39;re   you&#39;re   arguing   here   is   it   should   be   top   n   that   uses   nth   element   for   the   cases   that   on   average   it&#39;s   good   for,   and   then   it   switches   to   a   simple   reduction   that   just   has.
      </p>

        <cite>Bryce</cite>
      <time>21:31</time>
      <p>
          I   think   really   the   the   question   is   should   nth   element   implementations   special   case   the   like   the   case   of   two   elements   uh   or   the   case   of   one,   two,   and   like   three   elements.   And   actually   it   would   be   an   interesting   experiment   to   see   um   uh   what   the   cutoff   point   is   that   that   at   which   it   makes   sense   to   like   special   case.
      </p>

        <cite>Ben Deane</cite>
      <time>21:53</time>
      <p>
          The   other   observation   I   had   is   I   I   think   the   reduction   is   you   can   correct   me   on   this,   but   I   think   it&#39;s   by   necessity   giving   you   back   the   ordered   pair.   The   way   it   would   have   to   be   implemented.   Whereas   nth   element,   of   course,   doesn&#39;t   order   the   top   n   necessarily.
      </p>

        <cite>Conor</cite>
      <time>22:08</time>
      <p>
          Well,   it   depends.   So   like   in   the   parallel   version   where   you   have   the   associative   and   commutative   operation,   it   actually   will   be.
      </p>

        <cite>Ben Deane</cite>
      <time>22:18</time>
      <p>
          But   I   think   the   semantics,   yeah,   I   think   the   semantics   of   reducing   the   pair   mean   that   you   have   to   designate   one   as   the   higher   and   one   as   the   lower,   otherwise   you&#39;d   have   to   you   wouldn&#39;t.
      </p>

        <cite>Bryce</cite>
      <time>22:28</time>
      <p>
          Yeah,   well   wait,   but   why   why   wouldn&#39;t   why   wouldn&#39;t   the   nth   element   give   you   give   you   the   ordered   point?
      </p>

        <cite>Ben Deane</cite>
      <time>22:36</time>
      <p>
          Nth   element   doesn&#39;t   have   to   order   the.
      </p>

        <cite>Conor</cite>
      <time>22:38</time>
      <p>
          Because   it&#39;s   not   sorted.
      </p>

        <cite>Ben Deane</cite>
      <time>22:40</time>
      <p>
          It   might   end   up   ordering   a   pair.   I   don&#39;t   exactly   know.   But   if   you   ask   it   for   top   n,   it&#39;s   just   gonna   it&#39;s   gonna   pin   the   nth   element.   Everything   above   it   is   gonna   belong   above   it,   but   not   necessarily   in   the   right   order.
      </p>

        <cite>Conor</cite>
      <time>22:54</time>
      <p>
          So   the   the   API   for   nth   element   is   three   iterators,   the   beginning   of   the   range,   the   element   that   you   want   to   get   at   the   right   spot,   and   then   the   end   of   the   range.   And   the   only   thing   you&#39;re   guaranteed   is   that   everything   below   that   point,   your   nth   element   point   is   less   than,   or   whatever,   if   if   you&#39;re   using   the   default   comparator,   and   then   everything   above   it   is   greater.   And   then   you&#39;re   guaranteed   that   at   that   point   is   where   it   would   show   up   in   a   sort   of   thing.
      </p>

        <cite>Ben Deane</cite>
      <time>23:21</time>
      <p>
          If   it   were   ordered,   that   would   be   a   partial   sort,   right?   That&#39;s   that&#39;s   exactly.
      </p>

        <cite>Conor</cite>
      <time>23:26</time>
      <p>
          And   I   think   Kate   Gregory   actually   at   one   point,   she   in   one   of   her   talks   says   that   partial   sort   copy   should   be   called   top   n.   And   then   in   the   talk   that   I   later   gave,   I   pointed   out   that   actually   partial   sort   copy   should   be   called   top   n   sorted,   and   nth   element   copy   should   be   called   um   top   n   because   the   partial   sort   one   is   the   one   that   guarantees   that   your   your   top   n   are   going   to   be   sorted.
      </p>

        <cite>Bryce</cite>
      <time>23:46</time>
      <p>
          But   but   if   the   if   the   case   if   you&#39;re   using   nth   element   to   do   top   two,   doesn&#39;t   it   happen   to   be   the   case   that   that   that   it&#39;ll   be   in   order   just   for   that   case   of   top   two?
      </p>

        <cite>Ben Deane</cite>
      <time>23:59</time>
      <p>
          Yes.   Oh   yeah,   actually   that&#39;s   a   good   point.   But   but   I   guess   the   point   is   it   hasn&#39;t   done   any   extra   comparisons   to   make   that   the   case,   right?
      </p>

        <cite>Bryce</cite>
      <time>24:11</time>
      <p>
          I   just   meant   that   like   in   the   case   of   two,   it   like   it   does   sort   of   happen   to   be.   Um   yeah,   I   mean,   maybe,   maybe   Kate&#39;s,   I   I   don&#39;t   I   don&#39;t   think   that   we   need   a   top   n   element.   I   think   that   the   that   uh   uh   you   know   it   really   it&#39;s   just   you   either   use   nth   element   or   you   use   partial   sort   copy,   um,   depending   on   whether   you   want   them   ordered   or   not.   Um   but   but   the   this   this   case,   uh   this   question   of   um   special   casing   um   uh   you   know   for   some   of   these   lower   count   cases   is   in   is   an   interesting   one.   You   know,   a   lot   a   lot   of   the   a   lot   of   the   um   optimizations   that   we   end   up   doing   in   the   Cub   library,   which   is   our   library   of   um   algorithmic   primitives,   um   of   parallel   algorithmic   primitives   for   CUDA,   um,   a   lot   of   the   big   performance   wins   that   we   get   is   because   like   we   identify   a   special   case   that   you   know   happens   to   be   uh   easy   to   optimize   and   also   like   a   lot   of   people   just   fall   into   it.   So   almost   almost   every   algorithm   has   some   decision   tree   of   you   know   uh   if   it&#39;s   this   case,   you   do   this   thing,   and   otherwise   you   do   this   thing.
      </p>

        <cite>Ben Deane</cite>
      <time>25:30</time>
      <p>
          It&#39;s   I   I   have   long   considered   it   the   sort   of   most   unloved   algorithm   or   or   most   overlooked   algorithm.   Uh   and   as   you   know,   in   I   think   it   was   17,   um   the   complexity   boundaries   of   sort   were   tightened.   It   used   to   say   prior   to   seven,   I   think   it&#39;s   17,   right   maybe   14   or   even   11,   but   maybe   it   was   11.   Um   but   it   used   to   say   uh   n   log   n   on   average,   and   now   the   standard   says   sort   is   n   log   n,   period.   Right?
      </p>

        <cite>Bryce</cite>
      <time>26:06</time>
      <p>
          I   I   think   we   cleaned   that   up   in   17   because   we   we   cleaned   up   a   lot   of   the   complexities   when   we   added   the   parallel   algorithms   and   we   had   to   figure   out   the   complexities   for   them,   but   I   could   be   wrong.
      </p>

        <cite>Ben Deane</cite>
      <time>26:17</time>
      <p>
          The   same   cleanup   was   not   done   for   nth   element.   Nth   element   is   linear   on   average,   but   I   think   the   same   essentially   the   same   work,   which   is   the   work   of   um   Dave   Musser,   um   he   did   a   lot   of   work   on   this   uh   back   back   in   the   2000s,   I   think   it   was,   um,   that   that   led   to   intro   sort   that   Connor   was   talking   about   and   and   the   possibility   of   making   sort   n   log   n   on   average.   I   think   that   same   underlying   uh   that   same   underlying   work   uh   translates   to   making   nth   element   linear   period,   if   we   wanted   that.
      </p>

        <cite>Conor</cite>
      <time>26:56</time>
      <p>
          Someone&#39;s   gotta   write   a   paper.   Listener,   out   there   if   you&#39;re   interested   in   getting   involved   in   standard   committee   work.
      </p>

        <cite>Ben Deane</cite>
      <time>27:02</time>
      <p>
          Yeah,   because   intro   select   is   the   uh   algorithm   counterpart   to   for   n   element   that   for   for   intro   sort.
      </p>

        <cite>Conor</cite>
      <time>27:08</time>
      <p>
          Right,   right.   Yeah.   This   ends   part   one   of   what   will   probably   be   a   four   part   series   on   algorithms.   Thanks   for   listening.   We   hope   you   enjoy   and   have   a   great   day.
      </p>