optimizing many

- src/NameGame.h: update network to use linked list for memory (given
  macro). seems to provide ~2x speedup.
- src/NameGame.cc: add iterator for TLst type.
- add copy constructor and copy assignment operator for TLst that are
  not defined by the SNAP library.
- add TP_BESTMOVE_STATIC to use static array for voting to speed up
  best_move by ~2x.
- add conditional logic in places to allow for A/B testing.
- based off testing I can get ~4x total improvement so I think I will
  make both of these permanent (except maybe leaving in the old
  unoptimized code in case I want to add multiple strategies).
- TASKS.md: update tasks.

Signed-off-by: Aiden Woodruff <woodra@rpi.edu>

3 files changed, 83 insertions, 4 deletions

diff --git a/TASKS.md b/TASKS.md
index b5b145a..c4ac8c7 100644
--- a/TASKS.md
+++ b/TASKS.md
@@ -3,8 +3,6 @@
 ## To do
 
 - Profiling/optimizing `many`.
-    - Use static array for best_move.
-    - Use SNAP list for memory.
     - Divide and conquer multithreading.
 - Vary strategy selection behavior.
     - $exp(-i)$ weighting for memory?
diff --git a/src/NameGame.cc b/src/NameGame.cc
index 1454862..ed56f09 100644
--- a/src/NameGame.cc
+++ b/src/NameGame.cc
@@ -2,12 +2,61 @@
 #include <fstream>
 #include <iomanip>
 #include <iostream>
+#define TP_BESTMOVE_STATIC
+#ifndef TP_BESTMOVE_STATIC
 #include <map>
+#endif
 #include <stdexcept>
 #include <vector>
 
 #include "NameGame.h"
 
+#ifdef TP_MEMLIST
+template<typename TVal>
+class TLstIter {
+public:
+        TLstIter(typename TLst<TVal>::PLstNd nd_) : nd(nd_) {}
+        const TVal& operator*() const {
+                return nd->GetVal();
+        }
+        TVal& operator*() {
+                return nd->GetVal();
+        }
+        TLstIter<TVal>& operator++() {
+                nd = nd->Next();
+                return *this;
+        }
+        bool operator==(const TLstIter<TVal>& rhs) const {
+                return nd == rhs.nd;
+        }
+private:
+        typename TLst<TVal>::PLstNd nd;
+};
+
+template<typename TVal>
+TLstIter<TVal> begin(const TLst<TVal>& l) {
+        return TLstIter<TVal>(l.First());
+}
+
+template<typename TVal>
+TLstIter<TVal> end(const TLst<TVal>& l) {
+        return TLstIter<TVal>(nullptr);
+}
+
+template<typename TVal>
+TLst<TVal>::TLst(const TLst<TVal>& l) : TLst() {
+        for (const auto& val : l) AddBack(val);
+}
+
+template<typename TVal>
+TLst<TVal>& TLst<TVal>::operator=(const TLst<TVal>& l) {
+        if (this != &l) {
+                Clr();
+                for (const auto& val : l) AddBack(val);
+        }
+        return *this;
+}
+#else
 template<typename TVal, typename TSizeTy>
 auto begin(const TVec<TVal, TSizeTy>& v) -> decltype(v.BegI()) {
         return v.BegI();
@@ -17,6 +66,7 @@ template<typename TVal, typename TSizeTy>
 auto end(const TVec<TVal, TSizeTy>& v) -> decltype(v.EndI()) {
         return v.EndI();
 }
+#endif
 
 namespace tp {
 
@@ -61,7 +111,11 @@ void NameGame::initMemory() {
                 auto& rDat = graph.GetNDat(rId);
                 rDat.Val1 = true;
                 rDat.Val2.Clr();
+#ifdef TP_MEMLIST
+                rDat.Val2.AddFront(1);
+#else
                 rDat.Val2.Add(1);
+#endif
                 ids.erase(ids.begin() + r);
         }
         // Establish norm (fully memory of strategy 1) for remaining nodes.
@@ -69,7 +123,13 @@ void NameGame::initMemory() {
                 auto& d = graph.GetNDat(id);
                 d.Val1 = false;
                 d.Val2.Clr();
-                while (d.Val2.Len() < memlen) d.Val2.Add(-1);
+                while (d.Val2.Len() < memlen) {
+#ifdef TP_MEMLIST
+                        d.Val2.AddFront(-1);
+#else
+                        d.Val2.Add(-1);
+#endif
+                }
         }
 }
 
@@ -135,6 +195,14 @@ float weight(int i) {
 
 int NameGame::best_move(int nId) const {
         const auto& mem = graph.GetNDat(nId).Val2;
+#ifdef TP_BESTMOVE_STATIC
+        int votes[2] = {0, 0};
+        for (const auto& strategy : mem) {
+                if (strategy == -1) votes[0]++;
+                else votes[1]++;
+        }
+        return votes[0] > votes[1] ? -1 : 1;
+#else
 #ifdef USE_EXP_WEIGHT
         std::map<int, float> votes;
         for (int i = 0; i < mem.Len(); ++i) {
@@ -155,13 +223,19 @@ int NameGame::best_move(int nId) const {
                 }
         )->first;
         return best;
+#endif
 }
 
 void NameGame::update_memory(int nId, int strategy) {
         auto& d = graph.GetNDat(nId);
         if (!d.Val1) {
+#ifdef TP_MEMLIST
+                d.Val2.AddFront(strategy);
+                d.Val2.DelLast();
+#else
                 d.Val2.Ins(0, strategy);
                 d.Val2.Trunc(memlen);
+#endif
         }
 }
 
diff --git a/src/NameGame.h b/src/NameGame.h
index 0b02a15..21a58b8 100644
--- a/src/NameGame.h
+++ b/src/NameGame.h
@@ -34,7 +34,14 @@ private:
         int gsize, cmsize, memlen;
         std::mt19937 rng;
         std::uniform_int_distribution<> dist;
-        TNodeNet<TPair<TBool, TIntV>> graph;
+        TNodeNet<TPair<
+                TBool,
+#ifdef TP_MEMLIST
+                TIntL
+#else
+                TIntV
+#endif
+        >> graph;
         struct Record {
                 int round, speaker, committed, strategy;
         };