Some words that I always forget util I wrote it down: discipline collapse phantom

tags: High Performance,SIMD source: Lemire, Author Daniel. “Fast Bitset Decoding Using Intel AVX-512.” Daniel Lemire’s Blog (blog). Accessed May 12, 2022. https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/.

tags: Degree source: evanprodromou. “Master’s Degree in Computer Science.” Evan Prodromou’s Blog (blog), May 4, 2022. https://evanp.me/2022/05/04/masters-degree-in-computer-science/.

tags: Degree source: “【01B0801】 计算机及应用（独立本科段）.” Accessed May 6, 2022. http://zkxcx.bjeea.cn/portal/kszylb.jsp?zydm=01B0801&tab=2. Required Courses Code Name Credit Type Level1 Status2 Free Online Courses 03708 中国近现代史纲要 2 Political 5 pending 03708 马克思主义基本原理概论 4 Political 5 pending 00015 英语（二） 14 Basic 1 passed 00023 高等数学（工本） 10 Basic 7 pending 02197 概率论与数理统计（二） 3 Basic 7 pending 02324 离散数学 4 CS 7 pending 腾讯课堂 04737 C++程序设计 3 CS 1 pending 04738 C++程序设计（实践） 2 CS - pending 02326 操作系统 4 CS 2 pending 02327 操作系统（实践） 1 CS - pending 02331 数据结构 3 CS 2 pending 04734 数据结构（实践） 2 CS - pending 02325 计算机系统结构 4 CS 3 pending 04735 数据库系统原理 4 CS 1 pending 04736 数据库系统原理（实践） 2 CS - pending 02333 软件工程 3 CS 3 pending 02334 软件工程（实践） 1 CS - pending 04741 计算机网络原理 4 CS 2 pending 04747 Java语言程序设计（一） 3 CS 1 pending 04748 Java语言程序设计（一）（实践） 1 CS 1 pending 10027 计算机及应用专业毕业设计 0 CS 1 wait Summary: ...

tags: Degree, Career I haven’t got a CS degree, it wasn’t a big deal when I was yonger, as I was cheap and many employers could affort, and didn’t care too much about it. But now days, when I’m 30+ years old, and not cheap anymore. The employers who can affort me are much less. And most of them are required a CS degree, so the degree is important to me now. ...

tags: Degree source: Engineer, Lowly Midwestern. “My Experience Getting a Tech Job with No Degree or Relevant Work Experience.” Substack newsletter. Lowly Midwestern Engineers’ Newsletter (blog), May 2, 2022. https://lowlyswe.substack.com/p/my-experience-getting-a-tech-job.

tags: Degree source: “How I Got a Computer Science Degree in 3 Months for Less Than $5000 | Miguel Rochefort.” Accessed April 28, 2022. https://miguelrochefort.com/blog/cs-degree/.

tags: Career

tags: SIMD,High Performance source: “Luhn Algorithm Using SWAR and SIMD.” Accessed May 5, 2022. https://nullprogram.com/blog/2022/04/30/. 3x increase after used SIMD.

tags: SSE/AVX/AVX2/AVX512,High Performance source: Lemire, Author Daniel. “Removing Characters from Strings Faster with AVX-512.” Daniel Lemire’s Blog (blog). Accessed May 5, 2022. https://lemire.me/blog/2022/04/28/removing-characters-from-strings-faster-with-avx-512/. It’s 21.25 times faster with AVX-152: 0.4 GB/s to 8.5 GB/s.

tags: Emacs,GnuPG Pinentry,GnuPG,GnuPG Agent There is a little bit more background here: I’m using Windows Subsystem Linux(WSL) now, which means I was running Emacs in a virtual machine with Debian Linux distro. And also I ran Emacs in GUI mode with WSL, the pinentry for GnuPG Agent is: /usr/bin/pinentry-gtk2, everything was prefect. This morning I couldn’t commit with Magit in Emacs, when I was running my Emacs in Terminal Text Mode. The first thing I had done is change the pinentry: ...

tags: Unix,Tools

tags: GnuPG

tags: GnuPG,GnuPG Agent

tags: Data Structures,Algorithm

tags: Algorithm,Tree,Graph source: https://en.wikipedia.org/wiki/Minimum%5Fspanning%5Ftree

tags: High Performance source: https://en.wikipedia.org/wiki/Non-uniform_memory_access

tags: Linux,Network,Tools netstat -s: show network status(errors) # show udp status $ netstat -s --udp Udp: 437.0k/s packets received 0.0/s packets to unknown port received. 386.9k/s packet receive errors 0.0/s packets sent RcvbufErrors: 123.8k/s SndbufErrors: 0 InCsumErrors: 0

tags: Linux,Network,TCP,UDP,Tools ethtool -S: Reveal where the packets actuaaly went receiver$ watch 'sudo ethtool -S eth2 |grep rx' rx_nodesc_drop_cnt: 451.3k/s rx-0.rx_packets: 8.0/s rx-1.rx_packets: 0.0/s rx-2.rx_packets: 0.0/s rx-3.rx_packets: 0.5/s rx-4.rx_packets: 355.2k/s rx-5.rx_packets: 0.0/s rx-6.rx_packets: 0.0/s rx-7.rx_packets: 0.5/s rx-8.rx_packets: 0.0/s rx-9.rx_packets: 0.0/s rx-10.rx_packets: 0.0/s

tags: Linux,High Performance,Network,ethtool source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. What are Multi-queue NICs RX queue was used to pass packets between hardware and kernel. Now days NICs support multiple RX queues: Each RX queue is pinned to a separate CPU. Multi-queue hashing algorithms Use a hash from packet to decide the RX queue number. The hash is usually counted from a tuple (src IP, dst IP, src port, dst port). This guarantees that packets for a single flow will always end up on exactly the same RX queue, and reordering of packets within a single flow can’t happen. ...

tags: Network,Linux,Tools

tags: Network,UDP,High Performance,iptables,ethtool,netstat,NUMA source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. Keys: Make sure traffic won’t be interfered with by the iptables iptables -I INPUT 1 -p udp --dport 4321 -j ACCEPT iptables -t raw -I PREROUTING 1 -p udp --dport 4321 -j NOTRACK #+end_src[[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]] 2. The first bottleneck ​ + All packets are received by a signal RX queue, checked out with =ethtool -S=. ​ + How to solve: according to [[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]], change the hash algorithm with =ethtool=: #+begin_src bash ethtool -N eth2 rx-flow-hash udp4 sdfn Multiple threads with NUMA, and with multiple receiver ips to fit in multi-queue hash algorithm. Also note that there is a lock contention on the UDP receive buffer side, see Rivera, Diego, Eduardo Acha, Jose Piquer, and Javier Bustos-Jimenez. “Analysis of Linux UDP Sockets Concurrent Performance.” In 2014 33rd International Conference of the Chilean Computer Science Society (SCCC), 65–69. Talca: IEEE, 2014. https://doi.org/10.1109/SCCC.2014.8. ...

tags: Network

tags: Network

tags: Distributed Systems

tags: C/C++ Capture a map with reference If we capture a map by value, then we can’t use the operator []: unordered_map<int, int> freq; // Won't compile // auto comp_by_map = [freq](const int& a, const int& b) { return freq[a] < freq[b];}; auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b];};

tags: Hash Table,Heap (data structure),LeetCode101,Priority Queue,C++ Lambda class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> freq; // Note that: we need caputre a map by reference, // otherwise we can't use the operator[]. // See also: https://stackoverflow.com/a/6281071 auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b]; }; // Note that: here we need pass our lambda /comp_by_map/ to the // constructor of std::priority_queue. priority_queue<int, vector<int>, decltype(comp_by_map)> pq(comp_by_map); for (auto n: nums) { freq[n] = freq.find(n) == freq.end() ? 1 : freq[n] + 1; } for (auto iter: freq) { pq.push(iter.first); } while (k > 0) { res.push_back(pq.top()); pq.pop(); k--; } return res; } };

tags: LeetCode101,In-place Travel array in reverse order, and record how many times need to swap, which is how many elements not equal val. class Solution { public: int removeElement(vector<int>& nums, int val) { int k = 0; for (int j = nums.size() - 1; j >= 0; --j) { if (nums[j] == val) { for (int i = 0; i < k; ++i) { swap(nums[i + j], nums[j + i + 1]); } } else { k++; } } return k; } };

tags: Two Pointers,Three Pointers,LeetCode101,Sorting Based on: LeetCode101: 167. Two Sum II - Input Array Is Sorted LeetCode101: 15. 3Sum We create a new loop: class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int T, S, r, l; for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.size(); ++j) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } l = j + 1; r = nums.size() - 1; T = target - nums[i] - nums[j]; while (l < r) { S = nums[l] + nums[r]; if (S == T) { res.push_back({nums[i], nums[j], nums[l], nums[r]}); while (l < r && nums[l] == nums[l + 1]) { l++; } while (l < r && nums[r] == nums[r - 1]) { r--; } l++; r--; } else if (S < T) { l++; } else { r--; } } } } return res; } };

tags: Priority Queue,LeetCode101 Using a min heap to keep k elements, top is the Kth largest element. class KthLargest { private: // min heap priority_queue<int, vector<int>, std::greater<int>> pq; int K; public: KthLargest(int k, vector<int>& nums) { K = k; for (auto n: nums) { add(n); } } int add(int val) { pq.push(val); while (pq.size() > K) { pq.pop(); } return pq.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

tags: Heap (data structure),LeetCode101 Find top k values, classical heap problems. Here we need find top 2 values, and pop them from heap, then we will meet two cases: If they are not same, put back the differ between them, continue. Otherwise, continue directly.

tags: LeetCode101,Sorting,Two Pointers Key ideas: Move both sides to inwards. If the sum value less than target, move left pointer. Otherwise move right poinger. class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int S, l = 0, r = numbers.size() - 1; vector<int> res(2, 0); while (l < r) { S = numbers[l] + numbers[r]; if (S == target) { break; } if (S < target) { l++; } else { r--; } } res[0] = l + 1; res[1] = r + 1; return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas see LeetCode101: 15. 3Sum class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = INT_MAX, l, r, sum, T, res; for (int i = 0; i < nums.size(); i++) { l = i + 1; r = nums.size() - 1; T = target - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (abs(sum - T) < closest) { res = sum + nums[i]; closest = abs(sum - T); } if (sum == T) { return target; } if (sum < T) { l++; } else { r--; } } } return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas: Sort the nums first. Then, we travel the nums, pick current element as nums[i], and apply LeetCode101: 167. Two Sum II - Input Array Is Sorted to the remains. We skip the same numbers to avoid duplicate. class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int l, r, sum, T; vector<vector<int>> res; for (int i = 0; i < nums.size(); i++) { // Skip same numbers to avoid duplicate if(i > 0 && nums[i] == nums[i-1]) { continue; } l = i + 1; r = nums.size() - 1; T = 0 - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (sum == T) { res.push_back({nums[i], nums[l], nums[r]}); // Skip same numbers in each side to avoid duplicate while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum < T) { l++; } else { r--; } } } return res; } };

tags: Two Pointers

tags: String,Two Pointers,LeetCode101 Two pointers move inwards, when we meet two different characters: Remove left character to see if the remains string still satisfied a valid palindrome. Remove right character to see if the remains string still satisfied a valid palindrome. Returns true if either one above two is true. class Solution { public: bool validPalindrome(string s) { for (int i = 0, j = s.size() -1; i < j; i++,j--) { if (s[i] != s[j]) { // remove left auto left = isPalindrome(s, i + 1, j); // remove right auto right = isPalindrome(s, i, j - 1); // return at here as we have traveled the string in the // invocation of isPalindrome. return right || left; } } return true; } private: bool isPalindrome(string & s, int i, int j) { for (; i < j; i++,j--) { if (s[i] != s[j]) { return false; } } return true; } };

tags: In-place WikiPedia: https://en.wikipedia.org/wiki/In-place%5Falgorithm Let see two examples before we go further: As above we can see, to reverse a array in-place, we just need swap each two elements in the array from both side to middle. The pseudo code from WikiPedia: function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp The loop travels the array to the middle and swap each other in the list, two points we must be noticed: We stop the element at(not before): floor((n - 2) / 2), It’s both 1 of the two above figures. We swap current element with n - 1 - i.

tags: Algorithm

tags: In-place,LeetCode101,In-place Reverse class Solution { public: void reverseString(vector<char>& s) { if (s.size() == 1) { return; } for (int i = 0; i <= (s.size() - 2) / 2; ++i) { swap(s[s.size() - 1 - i], s[i]); } } };

tags: Binary Search,LeetCode101 There is three corner cases must be handled if we don’t find target in nums: Return r + 1 if target is greater than right. Or return mid + 1 if target is greater than mid. Otherwise return mid. class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = r / 2; while (l != r) { mid = l + (r - l) / 2; if (target == nums[mid]) { return mid; } if (target < nums[mid]) { r = mid; } else { l = mid + 1; } } if (target > nums[r]) { return r + 1; } if (target > nums[mid]) { return mid + 1; } return mid; } };

tags: Divide-and-Conquer,LeetCode101,Binary Search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = l + (r - l) / 2; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; } };

tags: Algorithm WIKIEPEDIA: https://en.wikipedia.org/wiki/Divide-and-conquer%5Falgorithm The points should been noted: The middle position is not (right - left) / 2, it must be left + ((right - left) / 2).

tags: Bit Manipulation,Bitwise Operator: XOR According to bitwise operator XOR: x ^ x = 0 y ^ 0 = y We apply the XOR operator to all the nums, all the same numbers will apply x ^ x = 0, and then y ^ 0 = y will result the single number. class Solution { public: int singleNumber(vector<int>& nums) { int xorN = 0; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { xorN ^= *iter; } return xorN; } };

tags: Algorithm

tags: Bitwise Operators 0101 (decimal 5) XOR 0011 (decimal 3) = 0110 (decimal 6) 0010 (decimal 2) XOR 1010 (decimal 10) = 1000 (decimal 8) Useful features: 1 ^ 1 = 0 2 ^ 0 = 2

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 Treat as A Linked List with circle According to the length of nums is n + 1, and integer range is [1, n], so we can treat each element as a index that point to some next value. For example: [1,3,4,2,2] It can be treated as(format is element(index)): 1(0) -> 3(1) -> 2(3) -> 4(3) -> 2(4) -> 4(3) We can see there is a circle in it, so: ...

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return nullptr; } // tortoise move 1 step auto slow = head->next; // hare move 2 steps auto fast = head->next->next; while (slow != fast) { if (slow == nullptr || fast == nullptr || fast->next == nullptr) { return nullptr; } slow = slow->next; fast = fast->next->next; } slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } };