Forem: Zaw Htut Win

C++ မှတ်စု ၃ - CPU cache ဆိုတာ ဘာလဲ။

Zaw Htut Win — Fri, 16 Jan 2026 03:24:09 +0000

Cache ဆိုတာ မြန်မာလို ပြောရရင်တော့ ခေတ္တယာယီနေရာပါ။

CPU မှာ L1, L2 နဲ့ L3 cache တွေရှိပါတယ်။ L1 နဲ့ L2 cache တွေက Core တိုင်းမှာ ပါပြီး L3 ကတော့ shared cache ပါ။ CPU ဟာ instruction တစ်ခုကို ဖတ်ရင် L1(32KB) မှာ အရင်ဖတ်တယ်။ L1 ကို အနီးဆုံး cache လို့ သဘောထားလို့ရပါတယ်။ သူ့ဆီက Data ယူရဖို့ ဆိုရင် CPU က 3-5 cycles လောက်နဲ့ ယူနိုင်ပါတယ်။ အလွန်မြန်တာပါ။ L1 မှာ instruction ကို မတွေ့ရင်တော့ CPU ဟာ L2 cache(256KB) မှာ ထပ်ရှာပါတယ်။ သူကတော့ 10-15 cycles လောက် CPU ကနေသွားရပါတယ်။ နောက်ဆုံး cache က L3 ပါ။ L3 ကိုရောက်ဖို့ကတော့ 50-100 cycles လောက်ကို CPU ကနေသွားရပါတယ်။ C++ မှာ Cache friendly ဖြစ်တဲ့ code အရှင်းဆုံးပုစ္ဆာက row major access လို့ခေါ်ပါတယ်။

အောက်ဖေါ်ပြပါcode က cache မဖြစ်တဲ့ code ပါ။

    for (int col = 0; col < N; col++) {
        for (int row = 0; row < N; row++) {
            sum += matrix[row][col];
        }
    }

ဟောသည် code ကတော့ cache efficent ဖြစ်ပါတယ်။ ဒါကို row major access လုပ်တယ်လို့ ခေါ်ပါတယ်။

    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            sum += matrix[row][col];
        }
    }

ဘာဖြစ်လို့ Row major access က cache friendly ဖြစ်တာလဲ။ကြည့်ကြရအောင်။ အောက်ပါ 2 dimentional array ကိုကြည့်ပါ။

int matrix[4][4] = {
    { 1,  2,  3,  4},  // row 0
    { 5,  6,  7,  8},  // row 1
    { 9, 10, 11, 12},  // row 2
    {13, 14, 15, 16}   // row 3
};

အဲဒီ array ဟာ memory ပေါ်မှာ နေရာယူရင် အောက်ပါအတိုင်းယူပါတယ်။

    matrix[0][0]  (1)  - 0x1000
    matrix[0][1]  (2)  - 0x1004
    matrix[0][2]  (3)  - 0x1008
    matrix[0][3]  (4)  - 0x100C
    matrix[1][0]  (5)  - 0x1010 
    matrix[1][1]  (6)  - 0x1014
    matrix[1][2]  (7)  - 0x1018
    matrix[1][3]  (8)  - 0x101C
    matrix[2][0]  (9)  - 0x1020
    matrix[2][1]  (10) - 0x1024
    matrix[2][2]  (11) - 0x1028
    matrix[2][3]  (12) - 0x102C
    matrix[3][0]  (13) - 0x1030
    matrix[3][1]  (14) - 0x1034
    matrix[3][2]  (15) - 0x1038
    matrix[3][3]  (16) - 0x103C

ဒီတော့ CPU က စ အလုပ်လုပ်တဲ့ အချိန်မှာ ဘာကိုသွားကြည့်လဲဆိုတော့ matrix[0][0] ရဲ့ address ကိုသွားကြည့်ပါတယ်။ L1, L2 နဲ့ L3 မှာ အဲဒီ address ရှိမရှိကြည့်တယ်။ မရှိတော့ 64 byte တိတိ Cache ထဲကို ထည့်လိုက်ပါတယ်။ ဒီနေရာမှာ တစ်ခုပြောစရာရှိတာက int တစ်လုံး က 4 byte ယူပါတယ်။

    matrix[0][0]  (1)  - 0x1000
    matrix[0][1]  (2)  - 0x1004

Cache ပေါ်မှာ 64 byte ရောက်သွားတယ်ဆိုတာ ခုဏကပြောတဲ့ 2 dimensional array တစ်ခုလုံး Cache ပေါ်ရောက်သွားတာပါ။ ဒါကြောင့် matrix[0][1] , matrix[0][2] အစရှိသဖြင့် loop ထဲကခေါ်သမျှဟာ Cache ထဲကနေ CPU က အသင့် memory address ကို 4 bytes စီတိုးပြီး ခေါ်သွားရုံမို့လို့ အများကြီး မြန်သွားပါတော့တယ်။

Tim Peter ရဲ့ Sort၊ TimSort

Zaw Htut Win — Thu, 15 Jan 2026 14:37:16 +0000

Java 24 မှာ Object Array တွေကို စီဖို့ Tim Peters Python သုံးပြီး ရေးခဲ့တဲ့ TimSort ကို သုံးပါတယ်။ TimSort ရဲ့ အလုပ်လုပ်ပုံက

// Facebook Feed Ranking လုပ်ငန်းစဉ်
class FacebookFeed {
    List<Post> getRankedFeed(User user) {
        List<Post> allPosts = collectPosts(user);

        // TimSort ရဲ့ အလုပ်လုပ်ပုံ:
        // 1. စီပြီးသား "runs" ရှာခြင်း
        allPosts = findNaturalRuns(allPosts);

        // 2. သေးငယ်သော runs များကို ပေါင်းခြင်း
        allPosts = mergeSmallRuns(allPosts);

        // 3. Optimized merging
        return optimizedMerge(allPosts);
    }
}

ဒီနေရာမှာ Peter ရဲ့ findNaturalRuns Algorithm နဲ့ ပါတ်သတ်ပြီးသူပြောခဲ့တာက Database log တွေကို TimeStamp တွေနဲ့ ရိုက်ကြတယ်။ Database record တွေကို primary key အနေနဲ့ သိမ်းကြတယ်။ ဒီ့အတွက် အဖြေက findNatualRuns ပါပဲတဲ့။ အောက်ဖေါ်ပြပါ ကုဒ်ကတော့ small runs တွေကို merge လုပ်တဲ့ပုံပါ။ Facebook ဥပမာပေးထားပါတယ်။

class FacebookFeedSorter {

    void processFeedUpdates() {
        // Initial: 100 posts (already sorted by time)
        Run run1 = new Run(0, 100);  // Old posts

        // User scrolls down: 20 new posts loaded
        Run run2 = new Run(100, 20); // New posts (timestamp sorted)

        // mergeSmallRuns လုပ်ငန်းစဉ်:
        stack.push(run1);
        stack.push(run2);

        // Check invariant:
        // run1.length = 100, run2.length = 20
        // Only one run in stack, no merge needed

        // More scrolling: 30 more posts
        Run run3 = new Run(120, 30);
        stack.push(run3);

        // Now stack has 3 runs: [100, 20, 30]
        // Check: 100 <= 20+30? 100 <= 50? ❌ (False - no merge)
        // Check: 20 <= 30? ✅ (True - invariant satisfied)
        // No merge needed!

        // User likes/shared - resort by engagement
        // New runs created, mergeSmallRuns efficiently merges them
    }
}

Tim က ရှိပြီးသား data တွေကို sorted ဖြစ်မဖြစ် အရင် detect လုပ်။ sort မဖြစ်သေးတာတွေကို small chunk အနေနဲ့ sort လုပ်။ ပြီးတော့ merge လုပ်တာပါ။

highestOneBit ဆိုတာဘာလဲ

Zaw Htut Win — Fri, 09 Jan 2026 17:25:32 +0000

x (decimal)	x (binary)	highestOneBit(x)
1	`0001`	1
5	`0101`	4
10	`1010`	8
15	`1111`	8

ဒီနေရာမှာ Highest one bit ဆိုတာ decimal 15 က binary မှာ 1111.

1 ရဲ့ ဘယ်ဘက်ဆုံးမှာ ရှိနေတဲ့ 1 က index 0 မှာ ရှိတယ်။ ဒါကြောင့် 2^0 ဆိုတော့ highest one bit က 2

5 ရဲ့ ဘယ်ဘက်ဆုံးမှာ ရှိနေတဲ့ 1 က index 2 မှာ ရှိတယ်။ ဒါကြောင့် 2^2 ဆိုတော့ highest one bit က 4

10 ရဲ့ ဘယ်ဘက်ဆုံးမှာ ရှိနေတဲ့ 1 က index 3 မှာ ရှိတယ်။ ဒါကြောင့် 2^3 ဆိုတော့ highest one bit က 8

15 ရဲ့ ဘယ်ဘက်ဆုံးမှာ ရှိနေတဲ့ 1 က index 3 မှာပဲ ရှိသေးတယ်။ ဒါကြောင့် 2^3 ဆိုတော့ highest one bit က 8

Java မှာ

Integer.highestOneBit(n);

ဆိုတဲ့ build in function ပါပါတယ်။

CPU-level optimization

Memory layouts

Predictable-performance code

တွေရေးတဲ့နေရာမှာ အသုံးများပါတယ်။

Cached HashMap for infinite insertions of entries

Zaw Htut Win — Fri, 09 Jan 2026 16:51:24 +0000

If you store infinite number of entries in the HashMap, Garbage Collector will not kickin. So at a certain point Out of Memory error will occured.

Below is the example(using VisualVM to profile the heap)

So I changed a few places inside the HashMap implemetation to allow the GC to kickin. The strategy is to use the CacheHashMap. Afer changing that my profile becomes like following.

As you can see above GC is regularly kicks-in. See the spikes, that's mean GC is doing it's job.


import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;

public class CachedHashMap<K,V> implements Map<K, V>
{
    private int maxEntries = 1000;
    private final LinkedList<K> insertionOrder = new LinkedList(); // track keys for eviction

    private static int nextPowerOfTwo(int n) 
    {
        if (n <= 1) return 1;
        return Integer.highestOneBit(n - 1) << 1;
    }

    private static int previousPowerOfTwo(int n) 
    {
        return Integer.highestOneBit(n);
    }

    private static class Entry<K, V> 
    {
        final int hash;
        final K key;
        V value;
        Entry<K, V> next;

        Entry(int hash, K key, V value, Entry<K, V> next) 
        {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private static final int    MIN_CAPACITY    = 16;
    private static final float  LOAD_FACTOR     = 0.75f;
    private static final float  SHRINK_FACTOR   = 0.25f;


    private Entry<K, V>[]   m_Table;
    private int             m_Size = 0;
    private int             m_Capacity;

    @SuppressWarnings("unchecked")
    public  CachedHashMap(int initialCapacity)
    {
        m_Capacity = nextPowerOfTwo(Math.max(MIN_CAPACITY, initialCapacity));
        m_Table = (Entry<K, V>[]) new Entry[m_Capacity]; //its fine...due to type erasure everything will get reduce to a common object ref

    }

    public  CachedHashMap(int initialCapacity,int maxEntries)
    {
        m_Capacity = nextPowerOfTwo(Math.max(MIN_CAPACITY, initialCapacity));
        m_Table = (Entry<K, V>[]) new Entry[m_Capacity]; //its fine...due to type erasure everything will get reduce to a common object ref
        this.maxEntries = maxEntries;
    }

    public CachedHashMap() 
    {
        this(MIN_CAPACITY);
    }

    public CachedHashMap(Map<? extends K, ? extends V> map) 
    {
        this(map != null ? map.size() : MIN_CAPACITY);
        if (map != null) 
        {
            putAll(map);
        }
    }

    public CachedHashMap(Collection<? extends Map.Entry<? extends K, ? extends V>> entries) 
    {
        this(entries != null ? entries.size() : MIN_CAPACITY);
        if (entries != null) 
        {
            for (Map.Entry<? extends K, ? extends V> entry : entries) 
            {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    public int size() 
    {
        return m_Size;
    }

    public int capacity()
    {
        return m_Capacity;
    }

    @Override
    public boolean isEmpty() 
    {
        return m_Size == 0;
    }

    @Override
    public Collection<V> values() 
    {
        List<V> values = new ArrayList<>();
        for (Entry<K, V> bucket : m_Table) 
        {
            Entry<K, V> e = bucket;
            while (e != null) 
            {
                values.add(e.value);
                e = e.next;
            }
        }
        return values;
    }

    @Override
    public boolean containsValue(Object value) 
    {
        for (Entry<K, V> bucket : m_Table) 
        {
            Entry<K, V> e = bucket;
            while (e != null) 
            {
                if (Objects.equals(e.value, value)) 
                {
                    return true;
                }
                e = e.next;
            }
        }
        return false;
    }

    @Override
    public boolean containsKey(Object key) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Capacity);

        for (Entry<K, V> e = m_Table[index]; e != null; e = e.next) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) {
                return true;
            }
        }
        return false;
    }

    public boolean hasKey(K key) 
    {
        return get(key) != null;
    }

    @Override
    public V get(Object key) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                return e.value;
            }
            e = e.next;
        }
        return null;
    }

    @Override
    public V getOrDefault(Object key, V defaultValue) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                return e.value;
            }
            e = e.next;
        }
        return defaultValue;
    }

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) 
    {
        if(action == null)
            return;

        for (Entry<K, V> bucket : m_Table) 
        {
            Entry<K, V> e = bucket;
            while (e != null) 
            {
                action.accept(e.key, e.value);
                e = e.next;
            }
        }
    }


    public V fetch(K key) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                return e.value;
            }
            e = e.next;
        }
        return null;
    }
    private boolean checkMapIsFull() {
        return m_Size > m_Capacity;
    }
    @Override
    public V put(K key, V value) 
    {


        int hash = hash(key); //compute hash
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        boolean isNewKey = true;

        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                V old = e.value;
                isNewKey = false;
                e.value = value;
                return old;
            }
            e = e.next;
        }

        if (isNewKey) {
            insertionOrder.addLast(key); // track order for eviction
        }        

        Entry<K, V> newEntry = new Entry<>(hash, key, value, m_Table[index]);
        m_Table[index] = newEntry;
        m_Size++;

        tryResize();    

        while (m_Size > maxEntries) {
            K oldest = insertionOrder.removeFirst();
            remove(oldest); // call your own remove method
        }

        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) 
    {
        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) 
        {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public V remove(Object key) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> prev = null;
        Entry<K, V> e = m_Table[index];

        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                if (prev == null) 
                {
                    m_Table[index] = e.next;
                } 
                else 
                {
                    prev.next = e.next;
                }

                V oldValue = e.value;

                e.next = null;
                e.value = null;
                e = null;

                m_Size--;
                tryResize();
                return oldValue;
            }
            prev = e;
            e = e.next;
        }
        return null;
    }

    public V removeKey(K key) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> prev = null;
        Entry<K, V> e = m_Table[index];

        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                if (prev == null) 
                {
                    m_Table[index] = e.next;
                } 
                else 
                {
                    prev.next = e.next;
                }

                V oldValue = e.value;

                e.next = null;
                e.value = null;
                e = null;

                m_Size--;
                tryResize();
                return oldValue;
            }
            prev = e;
            e = e.next;
        }
        return null;
    }



    public void clear() 
    {
        Arrays.fill(m_Table, null);
        m_Size = 0;
        tryResize(); //shrink to minimum
    }

    public Set<K> keySet() 
    {
        Set<K> keys = new HashSet<>();
        for (Entry<K, V> bucket : m_Table) 
        {
            Entry<K, V> e = bucket;
            while (e != null) 
            {
                keys.add(e.key);
                e = e.next;
            }
        }
        return keys;
    }

    public Set<Map.Entry<K, V>> entrySet() 
    {
        Set<Map.Entry<K, V>> entries = new HashSet<>();
        for (Entry<K, V> bucket : m_Table) 
        {
            Entry<K, V> e = bucket;
            while (e != null) 
            {
                entries.add(new AbstractMap.SimpleImmutableEntry<>(e.key, e.value));
                e = e.next;
            }
        }
        return entries;
    }

    public Iterator<Map.Entry<K, V>> iterator() 
    {
        return new EntryIterator();
    }

    private int hash(Object key) 
    {
        int h = key == null ? 0 : key.hashCode();
        return h ^ (h >>> 16); // same as HashMap spreader
    }

    private int indexFor(int hash, int length) 
    {
        return hash & (length - 1);
    }

    private void tryResize() ///grows or shrinks the map
    {
        if (m_Size > m_Capacity * LOAD_FACTOR) 
        {
            resize(nextPowerOfTwo(m_Capacity * 2));
        } 
        else if (m_Capacity > MIN_CAPACITY && m_Size < m_Capacity * SHRINK_FACTOR) 
        {
            //shrink to the nearest by halving down to the nearest power of 2
            resize(Math.max(previousPowerOfTwo(m_Capacity / 2), MIN_CAPACITY));
        }
    }

    @Override
    public boolean remove(Object key, Object value) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> prev = null;
        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, value)) 
            {
                if (prev == null) 
                {
                    m_Table[index] = e.next;
                } 
                else 
                {
                    prev.next = e.next;
                }
                m_Size--;
                tryResize();
                return true;
            }
            prev = e;
            e = e.next;
        }
        return false;
    }

    @Override
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) 
    {
        Objects.requireNonNull(mappingFunction);

        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                return e.value; // Already present
            }
            e = e.next;
        }

        V newValue = mappingFunction.apply(key);
        if (newValue != null) 
        {
            m_Table[index] = new Entry<>(hash, key, newValue, m_Table[index]);
            m_Size++;
            tryResize();
            return newValue;
        }
        return null;
    }

    @Override
    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 
    {
        Objects.requireNonNull(remappingFunction);

        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> prev = null;
        Entry<K, V> e = m_Table[index];

        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                V newValue = remappingFunction.apply(key, e.value);
                if (newValue == null) 
                {
                    // Remove
                    if (prev == null) m_Table[index] = e.next;
                    else prev.next = e.next;
                    m_Size--;
                    tryResize();
                    return null;
                } 
                else 
                {
                    e.value = newValue;
                    return newValue;
                }
            }
            prev = e;
            e = e.next;
        }

        V newValue = remappingFunction.apply(key, null);
        if (newValue != null) 
        {
            m_Table[index] = new Entry<>(hash, key, newValue, m_Table[index]);
            m_Size++;
            tryResize();
            return newValue;
        }
        return null;
    }



    @Override
    public V computeIfPresent(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) 
    {
        Objects.requireNonNull(remappingFunction);

        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);
        Entry<K, V> e = m_Table[index];

        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                V newValue = remappingFunction.apply(key, e.value);
                if (newValue == null) 
                {
                    remove(key);
                    return null;
                } else 
                {
                    e.value = newValue;
                    return newValue;
                }
            }
            e = e.next;
        }
        return null;
    }

    @Override
    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) 
    {
        Objects.requireNonNull(remappingFunction);

        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                V newValue = remappingFunction.apply(e.value, value);
                if (newValue == null) 
                {
                    remove(key); // Will trigger resize if needed
                    return null;
                }
                e.value = newValue;
                return newValue;
            }
            e = e.next;
        }

        if (value != null) 
        {
            m_Table[index] = new Entry<>(hash, key, value, m_Table[index]);
            m_Size++;
            tryResize();
            return value;
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) 
    {
        Entry<K, V>[] oldTable = m_Table;
        Entry<K, V>[] newTable = (Entry<K, V>[]) new Entry[newCapacity];

        for (Entry<K, V> e : oldTable)
        {
            while (e != null) 
            {
                Entry<K, V> next = e.next;
                int index = indexFor(e.hash, newCapacity);

                e.next = newTable[index];
                newTable[index] = e;
                e = next;
            }
        }
        m_Table     = newTable; //please garbage collect
        m_Capacity  = newCapacity;
    }

    private class EntryIterator implements Iterator<Map.Entry<K, V>> 
    {
        int bucketIndex = 0;
        Entry<K, V> current = null;

        public boolean hasNext() 
        {
            while (current == null && bucketIndex < m_Table.length) 
            {
                current = m_Table[bucketIndex++];
            }
            return current != null;
        }

        public Map.Entry<K, V> next() 
        {
            if (!hasNext()) 
                throw new NoSuchElementException();

            Entry<K, V> e = current;
            current = current.next;
            return new AbstractMap.SimpleImmutableEntry<>(e.key, e.value);
        }
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) 
            {
                e.value = newValue;
                return true;
            }
            e = e.next;
        }
        return false;
    }

    @Override
    public V replace(K key, V newValue) 
    {
        int hash = hash(key);
        int index = indexFor(hash, m_Table.length);

        Entry<K, V> e = m_Table[index];
        while (e != null) 
        {
            if (e.hash == hash && Objects.equals(e.key, key)) 
            {
                V oldValue = e.value;
                e.value = newValue;
                return oldValue;
            }
            e = e.next;
        }
        return null;
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 
    {
        if(function == null)
            return;

        for (int i = 0; i < m_Table.length; i++) 
        {
            Entry<K, V> e = m_Table[i];
            while (e != null) 
            {
                e.value = function.apply(e.key, e.value);
                e = e.next;
            }
        }
    }

}

This is my Cached HashMap implementation. The thing is to use the bounded list.

boolean isNewKey = true;
....
if (isNewKey) {
            insertionOrder.addLast(key); // track order for eviction
}
....
while (m_Size > maxEntries) {
   K oldest = insertionOrder.removeFirst();
   remove(oldest); // call your own remove method
}

This will be useful if the incoming data are infinite and map doesn't need to hold historical data. It's FIFO based.

EventBus

Zaw Htut Win — Fri, 09 Jan 2026 07:43:27 +0000


import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;

// Concrete EventBus implementation
public class SimpleEventBus<T> implements MyEventBus<T> {

    private final ConcurrentHashMap<String, List<MyEventListener<T>>> listenersMap = new ConcurrentHashMap<>();

    // Publish an event to all listeners of a source
    public void push(String source, T event) {
        List<MyEventListener<T>> listeners = listenersMap.get(source);
        if (listeners != null && !listeners.isEmpty()) {
            for (MyEventListener<T> listener : listeners) {
                try {
                    listener.onEvent(source, event);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }

    // Get number of subscribers for a source
    public int getSubscriberCount(String source) {
        List<MyEventListener<T>> listeners = listenersMap.get(source);
        return (listeners == null) ? 0 : listeners.size();
    }

    @Override
    public void subscribe(String source, MyEventListener<T> listener) {
        listenersMap.computeIfAbsent(source, key -> new CopyOnWriteArrayList<>()).add(listener);
    }

    @Override
    public void unsubscribe(String source, MyEventListener<T> listener) {
        listenersMap.computeIfPresent(source, (key, list) -> {
            list.remove(listener);
            return list.isEmpty() ? null : list;
        });
    }
}

အထက်ပေါ်ပြပါ EventBus မှာ Guava ၏ EventBus နှင့်ဆင်တူသော EventBus implementation ဖြစ်သည်။ အထူးတလည်ပင်ရှင်းပြရန်မလိုပေ။

class MessageListener implements MyEventListener<Message> {
    private final String name;

    public MessageListener(String name) { this.name = name; }

    @Override
    public void onEvent(String source, Message event) {
        System.out.println(name + " received from [" + source + "]: " + event.getText());
    }
}

C++ မှတ်စု (၂) – Pointer နဲ့ Dereferencing

Zaw Htut Win — Mon, 28 Jul 2025 15:41:04 +0000

ခုဏက memory address ကို ကြည့်တဲ့ နည်းကို ပြခဲ့ပါတယ်။ ဒီတခါတော့ အဲ့ဒီ memory address မှာ ရှိနေတဲ့ value ကို pointer သုံးပြီး ကြည့်ကြည့်ရအောင်။

#include <iostream>
int main() {
    int i = 10;
    int* v = &i; 
    std::cout << "value of pointer v:"<< *v;
    return 0;
}

ဒါဆိုရင် Console မှာ အောက်ပါ output ကို မြင်ရမှာပါ။

  value of pointer v: 10

အထက်ပါ code က

std::cout << "value of pointer v:"<< *v;

ဒီလိုင်းက int pointer v က dereference လုပ်တာပါ။ သူ့ထဲမှာ i ရဲ့ address ကို သိမ်းထားလိုက်တာ။ ဒါကြောင့် *v ကို print လုပ်တဲ့အချိန်မှာ i ရဲ့ value ဖြစ်တဲ့ 10 ကို ပြနေတာပါ။

တကယ်လို့ *v = 12; လို့ assign လုပ်လိုက်ရင် i ရဲ့တန်ဖိုးပါ ပြောင်းသွားမှာပါ။
ဘာလို့လဲဆိုတော့ v ဟာ i ရဲ့ memory address ကို သိမ်းထားတဲ့ pointer ဖြစ်နေလို့ပါ။

#include <iostream>
int main() {
    int i = 10;
    int* v = &i; 
    std::cout << "value of pointer v:"<< *v;
    *v = 12;
    std::cout << "value of i:"<< i; 
    return 0;
}

ဒါဆိုရင် Console မှာ အောက်ပါအတိုင်း output ထွက်လာပါလိမ့်မယ်။

value of pointer v: 10
value of i: 12

C++ မှတ်စု (၁) – Output နဲ့ Memory Address

Zaw Htut Win — Mon, 28 Jul 2025 15:22:10 +0000

အောက်ပါ code က

#include <iostream>
int main() {
    int i = 10;
    std::cout << "output: " << i;
    return 0;
}

ဆိုရင် Console ပေါ်မှာ အောက်ပါ output ကို မြင်ရမှာ ဖြစ်ပါတယ်။

output: 10

ထူးဆန်းတာ တစ်ခုပြောပြရမယ်ဆိုရင် C++ မှာ variable တွေရဲ့ memory address ကို ကြည့်ချင်ရင် ကြည့်လို့ ရပါတယ်။

#include <iostream>
int main() {
    int i = 10;
    std::cout << "memory address of i: " << &i;
    return 0;
}

အပေါ်က code မှာ &i ဆိုတာက i variable ရဲ့ memory address ကို ပြတာပါ။ ဥပမာ

memory address of output: 0x61fe14

ဒါမျိုးကို မြင်ရမှာပါ။

မှတ်ချက်
(memory address ဟာ computer တခုနဲ့ တခု တူမှာမဟုတ်ပါဘူး။)

အခန်း(၆) Stack and it's usage(Data Structures in Action)

Zaw Htut Win — Mon, 14 Jul 2025 03:32:24 +0000

Stack ဆိုတဲ့ Data structure ကို language တွေတော်တော်များများမှာ အသုံးများပါတယ်။ Java မှ မဟုတ်ပါဘူး။

Stack တွေဟာ အပေါ်ဆုံးမှာ data ကို တင်လေ့ရှိပြီး အပေါ်ဆုံးကနေပဲ ပြန်ယူတတ်ကြတယ်။ ဥပမာ method a , b , c ကို stack ပေါ်တစ်ခုချင်းစီ တင်သွားရင် ပြန်ထုတ်တဲ့အခါ c , b , a ဆိုပြီး အပေါ်ဆုံးက c က အရင် ပြီးတော့မှ b နောက်ဆုံး a ရယ်လို့ ပြန်ထွက်လာမှာပါ။

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> callStack = new Stack<>();

        callStack.push("a()");
        callStack.push("b()");
        callStack.push("c()");

        System.out.println("Stack Top to Bottom:");
        while (!callStack.isEmpty()) {
            System.out.println("Calling: " + callStack.pop());
        }
    }
}

သူ့ရဲ့ console output က

Stack Top to Bottom:
Calling: c()
Calling: b()
Calling: a()

Stack ကို အများဆုံးသုံတဲ့ နေရာကတော့ stack frame ပါ။
ဒါဆို Stack အကြောင်းတော့ သိသွားပြီ။ Stack frame ဆိုတာ ဘာလဲဆိုတာ ကြည့်ရအောင်။Stack Frame ဆိုတာ method တစ်ခုကို ခေါ်လိုက်တိုင်း jvm က frame တစ်ခုကို Stack ထဲတင်လိုက်တာကို ပြောတာပါ။ အလွယ်ဆုံးပြောရရင် error တက်လို့ stack trace တက်လာရင် ပြတဲ့ console output ဟာ stack frame entries တွေပါပဲ။

public class StackTraceDemo {

    public static void main(String[] args) {
        methodA();
    }

    static void methodA() {
        methodB();
    }

    static void methodB() {
        methodC();
    }

    static void methodC() {
        int result = 10 / 0; // Will cause ArithmeticException
    }
}

Error output ္ထွက်လာရင် method C က အရင်ဆုံးပြတာကိုတွေ့ရမယ်။

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at StackTraceDemo.methodC(StackTraceDemo.java:15)
    at StackTraceDemo.methodB(StackTraceDemo.java:11)
    at StackTraceDemo.methodA(StackTraceDemo.java:7)
    at StackTraceDemo.main(StackTraceDemo.java:3)

Recursive function တွေမှာ တခါတလေ မှားရေးမိရင် stack frame တွေ တစ်ခုပေါ်တခုထပ်ပြီး infinite ဖြစ်သွားပါတယ်။ နောက်ဆုံးမှာ stack overflow ဖြစ်သွားတယ်ဆိုတဲ့ အကြောင်းရင်းကလည်း ဒါ့ကြောင့်ပါပဲ။

public class StackOverflowDemo {

    static void recursiveCall() {
        recursiveCall(); // infinite recursion
    }

    public static void main(String[] args) {
        recursiveCall();
    }
}

Error output ္ထွက်လာရင်

Exception in thread "main" java.lang.StackOverflowError
    at StackOverflowDemo.recursiveCall(StackOverflowDemo.java:4)
    ...

ဒီလောက်ဆို Stack Data Structure နဲ့ jvm ရဲ့ stack frame အကြောင်း သဘောပေါက်လိမ့်မယ်ထင်ပါတယ်။

အခန်း(၅) ThreadPoolExecutor နဲ့ တွဲသုံးတဲ့ Datastructure များ(Data Structures in Action)

Zaw Htut Win — Mon, 14 Jul 2025 01:42:00 +0000

ThreadPoolExecutor သုံးတဲ့ Queue က Blocking Queue အမျိုးအစားဝင်တွေထဲက ဖြစ်ပါတယ်။

ExecutorService pool = Executors.newFixedThreadPool(10);

ဒါက သူ့ default constructor ကိုခေါ်ထားတာ။

return new ThreadPoolExecutor(
    nThreads, nThreads,
    0L, TimeUnit.MILLISECONDS,
    new LinkedBlockingQueue<Runnable>()
);

ThreadPoolExecutors ဆိုတာက utility class ဖြစ်ပြီးတော့ ဒီနေရာမှာ သူ့ရဲ့ Blocking Queue အမျိုးအစားက LinkedBlockingQueue ကို default အနေနဲ့သုံးတာပါ။ အထက်ဖေါ်ပြပါ code က newFixedThreadPool(10) လို့ခေါ်လိုက်ရင် ထွက်လာမယ့် Executor object ပါ။ LinkedBlockingQueue ကိုနောက်များမှ ဖေါ်ပြပါ့မယ်။

ExecutorService executor = Executors.newCachedThreadPool();

ဒါက သူ့ default constructor ကိုခေါ်ထားတာ။

return new ThreadPoolExecutor(
    0,                        // corePoolSize
    Integer.MAX_VALUE,        // maximumPoolSize
    60L, TimeUnit.SECONDS,    // idle threads die after 60s
    new SynchronousQueue<Runnable>()  // workQueue
);

ဒီတခါလည်း ThreadPoolExecutor ကို သုံးပြီး SynchronousQueue ကို default အနေနဲ့ သုံးထားတာကို တွေ့ရမှဖြစ်ပါတယ်။

ExecutorService executor = Executors.newSingleThreadExecutor();

ဒါက သူ့ default constructor ကိုခေါ်ထားတာ။

return new FinalizableDelegatedExecutorService(
    new ThreadPoolExecutor(
        1,                            // corePoolSize
        1,                            // maximumPoolSize
        0L, TimeUnit.MILLISECONDS,    // no idle timeout
        new LinkedBlockingQueue<Runnable>()  // task queue
    )
);

ဒါက ThreadPoolExecutorService ထဲက သူ့ရဲ့ implementation ဖြစ်ပါတယ်။

ပြန်ကြည့်မယ်ဆိုရင်
newFixedThreadPool က LinkedBlockingQueue
newCachedThreadPool က SynchronousQueue
newSingleThreadExecutor က LinkedBlockingQueue
ဆိုတဲ့ Queue Data Structures တွေကို သုံးသွားတာကို မြင်တွေ့နိုင်မှာဖြစ်ပါတယ်။

အပိုင်း(၄)- HashMap ထဲက Node များအကြောင်း (Data Structures in Action)

Zaw Htut Win — Mon, 14 Jul 2025 01:34:34 +0000

Node<K,V>[] table;//internal array of hashmap

HashMap ရဲ့ အထဲမှာ Node တွေကို သိမ်းတဲ့ table array ရှိပါတယ်။ ယခင် bix ming က h ကို အောက်ပါအတိုင်း လုပ်ရင် array ရဲ့ index ကို ရတာပါ။ index ညွုန်ထားတဲ့ အခန်းကို bucket လို့ခေါ်ပါတယ်။

int index = (n - 1) & hash

HashMap မှာ internal array တစ်ခုတည်းရှိတာကို သတိချပ်ပါ။
Node မှာ Linked List တစ်ခုလုံးကို ညွုန်တာပါ။ ဒီနေရာမှာ သိထားဖို့က Linked list တခုလုံးကို ညွုန်တယ်ဆိုတာ Linked List ရဲ့ root node ကို သိမ်းပြီး လိုမှ next နဲ့ ပြန်ယူတာ (traverse) လုပ်တာကို ဆိုလိုတာပါ။

TreeNode မှာတော့ Red Black Tree ကို သိမ်းပါတယ်။ ထို့အတူပါပဲ root node ကို သိမ်းတာပါ။

Linked List နဲ့ Red Black Tree treversal ကိုတော့ ချန်လှပ်ထားပါမယ်။ သူတို့က တခြား လေ့လာရမယ့် data structures တွေမို့ပါ။

What I've learnt from MEXC web service that used google protobuf (There are not enough resources on the internet yet)

Zaw Htut Win — Wed, 02 Jul 2025 09:10:47 +0000

Sometimes there is a point whereby the chatgpt cannot think of and api documentation is lacking the detail that you need. That's what I've learnt from MEXC api documentation.

Note: Don't refer to this https://github.com/mexcdevelop/websocket-proto. You will get stuck because its giving out wrong information.

They specified that their webservice will use the .pb which is Google Protobuf but there is no .proto file in the documentation to compile. So I spend two days banging my head generating the required protofile for Orderbook. Chatgpt gave me the wrong answer citing the internet resource. Can't blame it either since the resources were limited. Then I use this tool https://protogen.marcgravell.com/decode to adjust the output and came up with the order book proto file as following.

syntax = "proto3";

option java_outer_classname = "MEXCDeltaProtocolV3";

message Bid {
  string price = 1;
  string quantity = 2;
}

message Ask {
  string price = 1;
  string quantity = 2;
}

message DepthEntry {
  repeated Bid bids = 1;
  repeated Ask asks = 2;

  string eventtype = 3;
  string version = 4;
}

message MEXCDeltaProtocolV3 {
  string channel = 1;
  string symbol = 3;
  int64 timestamp = 6;
  repeated DepthEntry entries = 313;
}

Timestamp for this request is outside of the recvWindow.

Zaw Htut Win — Mon, 30 Jun 2025 05:58:11 +0000

Go to

https://www.epochconverter.com/

Enter your computer time below and click "Human Date to Timestamp"

Copy and use that in Postman.