{"action":"created","comment":{"url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/comments/155001669","pull_request_review_id":81247453,"id":155001669,"diff_hunk":"@@ -1,82 +1,137 @@\n /**\n  * cache_tag_array.h\n  * Header for the cache tag array model.\n- * MIPT-MIPS Assignment 5.\n- * Ladin Oleg.\n+ * @author Oleg Ladin, Denis Los\n  */\n \n-/* Protection from multi-including. */\n #ifndef CACHE_TAG_ARRAY_H\n #define CACHE_TAG_ARRAY_H\n \n-/* C++ libraries. */\n-#include <list>\n-#include <vector>\n \n-/* Simulator modules. */\n #include <infra/types.h>\n #include <infra/log.h>\n+#include <infra/macro.h>\n+\n+#include <vector>\n+#include <unordered_map>\n+#include <utility>\n+#include <list>\n+\n \n-/* Replacement algorithm modules (LRU). */\n-class LRUInfo\n+\n+// Replacement algorithm modules (LRU)\n+class  LRUCacheInfo\n {\n-    /*\n-     * \"lru\" contains sequences of using for each set. First number in set list\n-     * is the least used.\n-     */\n-    std::vector< std::list< uint32>> lru = {};\n-\n-public:\n-    LRUInfo( uint32 ways, uint32 sets);\n-    void touch( uint32 set, uint32 way);\n-    uint32 update( uint32 set);\n+    public:\n+        explicit LRUCacheInfo( std::size_t capacity)\n+            : CAPACITY( capacity)\n+        {\n+            assert( capacity != 0u);\n+\n+            lru_hash.reserve( CAPACITY);\n+        }\n+\n+        auto get_capacity() const { return CAPACITY; }\n+        auto size() const { return number_of_elements; }\n+        bool empty() const { return size() == 0u; }\n+\n+        void touch( std::size_t key);\n+        std::size_t update();\n+\n+\n+    private:\n+        std::list<std::size_t> lru_list{};\n+        std::unordered_map<std::size_t, typename std::list<std::size_t>::const_iterator> lru_hash{};\n+\n+        std::size_t number_of_elements = 0u;\n+        std::size_t CAPACITY;\n };\n \n-class CacheTagArrayCheck : private Log\n+\n+\n+class LRUModule\n {\n-protected:\n-    CacheTagArrayCheck( uint32 size_in_bytes,\n-                        uint32 ways,\n-                        uint32 line_size,\n-                        uint32 addr_size_in_bits);\n-public:\n-        const uint32 size_in_bytes;\n-        const uint32 ways;\n-        const uint32 line_size;\n-        const uint32 addr_size_in_bits;\n+    public:\n+        LRUModule( std::size_t number_of_sets, std::size_t number_of_ways)\n+            : lru_info( number_of_sets, LRUCacheInfo( number_of_ways))\n+        { }\n+\n+        void touch( uint32 num_set, uint32 num_way) { lru_info[ num_set].touch( num_way); }\n+        \n+        uint32 update( uint32 num_set) { return lru_info[ num_set].update(); }\n+\n+    private:\n+        std::vector<LRUCacheInfo> lru_info;\n };\n \n-class CacheTagArray : public CacheTagArrayCheck\n+\n+\n+\n+\n+\n+// Cache tag array module implementation\n+class CacheTagArrayCheck : private Log\n {\n-    private:\n-        /* The set (line) of the cache. */\n-        struct CacheTag\n-        {\n-            Addr line = 0; // data\n-            bool is_valid = false; // validity\n-        };\n+    protected:\n+        CacheTagArrayCheck( uint32 size_in_bytes,\n+                            uint32 ways,\n+                            uint32 size_of_line,\n+                            uint32 addr_size_in_bits);\n+};\n \n-        const uint32 num_sets;\n-        const Addr   addr_mask;\n \n-        std::vector<std::vector<CacheTag>> array; // array of tags\n-        LRUInfo lru; // LRU algorithm module\n \n+class CacheTagArray : public CacheTagArrayCheck\n+{\n     public:\n-        CacheTagArray( uint32 size_in_bytes,\n+        CacheTagArray( uint32 size_in_bytes, \n                        uint32 ways,\n-                       uint32 line_size = 4,\n-                       uint32 addr_size_in_bits = 32);\n+                       uint32 size_of_line = 4,\n+                       uint32 addr_size_in_bits = 32)\n+\n+            : CacheTagArrayCheck( size_in_bytes, \n+                                  ways,\n+                                  size_of_line,\n+                                  addr_size_in_bits)\n+            , number_of_sets( size_in_bytes / ( ways * size_of_line))\n+            , number_of_ways( ways)\n+            , line_size( size_of_line)\n+            , addr_mask( bitmask<Addr>( addr_size_in_bits))\n+            , ways_to_tags( number_of_sets, std::unordered_map<uint32, Addr>{})\n+            , data( number_of_sets, std::unordered_map<Addr, uint32>{})\n+            , lru_module( number_of_sets, number_of_ways) \n+        { \n+            for ( std::size_t i = 0; i < number_of_sets; i++)\n+            {\n+                data[i].reserve( number_of_ways);\n+                ways_to_tags[i].reserve( number_of_ways);\n+            }    \n+        }\n \n-        /* lookup the cache and update LRU info */\n+        // lookup the cache and update LRU info\n         std::pair<bool, uint32> read( Addr addr);\n-        /* find in the cache but do not update LRU info */\n+        // find in the cache but do not update LRU info\n         std::pair<bool, uint32> read_no_touch( Addr addr) const;\n-        /* create new entry in cache */\n+        // create new entry in cache\n         uint32 write( Addr addr);\n \n-        uint32 set( Addr addr) const;\n-        Addr tag( Addr addr) const;\n+        uint32 set( Addr addr) const \n+        { \n+            return ( ( addr & addr_mask) / line_size) & (number_of_sets - 1); \n+        }\n+        Addr tag( Addr addr) const { return ( addr & addr_mask) / line_size; }\n+\n+    private:\n+        const uint32 number_of_sets;\n+        const uint32 number_of_ways;\n+        const uint32 line_size;\n+        const Addr   addr_mask;\n+\n+        // maps to convert num_ways to tags\n+        std::vector<std::unordered_map<uint32, Addr>> ways_to_tags;","path":"simulator/infra/cache/cache_tag_array.h","position":181,"original_position":181,"commit_id":"f906c737dfe17f39a64c2fa9732ee690369fdb3b","original_commit_id":"8e0fe9920526fac03ca36be1ee7ca0ed7f24d0df","user":{"login":"pavelkryukov","id":11466405,"avatar_url":"https://avatars3.githubusercontent.com/u/11466405?v=4","gravatar_id":"","url":"https://api.github.com/users/pavelkryukov","html_url":"https://github.com/pavelkryukov","followers_url":"https://api.github.com/users/pavelkryukov/followers","following_url":"https://api.github.com/users/pavelkryukov/following{/other_user}","gists_url":"https://api.github.com/users/pavelkryukov/gists{/gist_id}","starred_url":"https://api.github.com/users/pavelkryukov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pavelkryukov/subscriptions","organizations_url":"https://api.github.com/users/pavelkryukov/orgs","repos_url":"https://api.github.com/users/pavelkryukov/repos","events_url":"https://api.github.com/users/pavelkryukov/events{/privacy}","received_events_url":"https://api.github.com/users/pavelkryukov/received_events","type":"User","site_admin":false},"body":"It can be a ```std::vector<std::vector<Addr>>```, right?","created_at":"2017-12-05T16:31:01Z","updated_at":"2017-12-05T16:33:03Z","html_url":"https://github.com/MIPT-ILab/mipt-mips/pull/257#discussion_r155001669","pull_request_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257","author_association":"MEMBER","_links":{"self":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/comments/155001669"},"html":{"href":"https://github.com/MIPT-ILab/mipt-mips/pull/257#discussion_r155001669"},"pull_request":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257"}}},"pull_request":{"url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257","id":156058874,"html_url":"https://github.com/MIPT-ILab/mipt-mips/pull/257","diff_url":"https://github.com/MIPT-ILab/mipt-mips/pull/257.diff","patch_url":"https://github.com/MIPT-ILab/mipt-mips/pull/257.patch","issue_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/257","number":257,"state":"open","locked":false,"title":"Make CacheTagArray great again (#221, #225)","user":{"login":"denislos","id":22562510,"avatar_url":"https://avatars3.githubusercontent.com/u/22562510?v=4","gravatar_id":"","url":"https://api.github.com/users/denislos","html_url":"https://github.com/denislos","followers_url":"https://api.github.com/users/denislos/followers","following_url":"https://api.github.com/users/denislos/following{/other_user}","gists_url":"https://api.github.com/users/denislos/gists{/gist_id}","starred_url":"https://api.github.com/users/denislos/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/denislos/subscriptions","organizations_url":"https://api.github.com/users/denislos/orgs","repos_url":"https://api.github.com/users/denislos/repos","events_url":"https://api.github.com/users/denislos/events{/privacy}","received_events_url":"https://api.github.com/users/denislos/received_events","type":"User","site_admin":false},"body":"I have created BPUCache.h and LRUTagCache.h to implement BPU cache. I have also created some unit tests for it. Actually, there are still tests (`read_no_touch` test, `write` test, etc) to be created because I have added virtually only those ones which are tailored to the `LRUTagCache`.","created_at":"2017-12-03T12:41:17Z","updated_at":"2017-12-05T16:33:03Z","closed_at":null,"merged_at":null,"merge_commit_sha":"e49ddff44f2069fb169c2df07e98915366a5b813","assignee":null,"assignees":[],"requested_reviewers":[],"milestone":null,"commits_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257/commits","review_comments_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257/comments","review_comment_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/comments{/number}","comments_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/257/comments","statuses_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/statuses/f906c737dfe17f39a64c2fa9732ee690369fdb3b","head":{"label":"denislos:lru","ref":"lru","sha":"f906c737dfe17f39a64c2fa9732ee690369fdb3b","user":{"login":"denislos","id":22562510,"avatar_url":"https://avatars3.githubusercontent.com/u/22562510?v=4","gravatar_id":"","url":"https://api.github.com/users/denislos","html_url":"https://github.com/denislos","followers_url":"https://api.github.com/users/denislos/followers","following_url":"https://api.github.com/users/denislos/following{/other_user}","gists_url":"https://api.github.com/users/denislos/gists{/gist_id}","starred_url":"https://api.github.com/users/denislos/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/denislos/subscriptions","organizations_url":"https://api.github.com/users/denislos/orgs","repos_url":"https://api.github.com/users/denislos/repos","events_url":"https://api.github.com/users/denislos/events{/privacy}","received_events_url":"https://api.github.com/users/denislos/received_events","type":"User","site_admin":false},"repo":{"id":108724449,"name":"mipt-mips","full_name":"denislos/mipt-mips","owner":{"login":"denislos","id":22562510,"avatar_url":"https://avatars3.githubusercontent.com/u/22562510?v=4","gravatar_id":"","url":"https://api.github.com/users/denislos","html_url":"https://github.com/denislos","followers_url":"https://api.github.com/users/denislos/followers","following_url":"https://api.github.com/users/denislos/following{/other_user}","gists_url":"https://api.github.com/users/denislos/gists{/gist_id}","starred_url":"https://api.github.com/users/denislos/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/denislos/subscriptions","organizations_url":"https://api.github.com/users/denislos/orgs","repos_url":"https://api.github.com/users/denislos/repos","events_url":"https://api.github.com/users/denislos/events{/privacy}","received_events_url":"https://api.github.com/users/denislos/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/denislos/mipt-mips","description":"Cycle-accurate pre-silicon simulator of MIPS CPU","fork":true,"url":"https://api.github.com/repos/denislos/mipt-mips","forks_url":"https://api.github.com/repos/denislos/mipt-mips/forks","keys_url":"https://api.github.com/repos/denislos/mipt-mips/keys{/key_id}","collaborators_url":"https://api.github.com/repos/denislos/mipt-mips/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/denislos/mipt-mips/teams","hooks_url":"https://api.github.com/repos/denislos/mipt-mips/hooks","issue_events_url":"https://api.github.com/repos/denislos/mipt-mips/issues/events{/number}","events_url":"https://api.github.com/repos/denislos/mipt-mips/events","assignees_url":"https://api.github.com/repos/denislos/mipt-mips/assignees{/user}","branches_url":"https://api.github.com/repos/denislos/mipt-mips/branches{/branch}","tags_url":"https://api.github.com/repos/denislos/mipt-mips/tags","blobs_url":"https://api.github.com/repos/denislos/mipt-mips/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/denislos/mipt-mips/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/denislos/mipt-mips/git/refs{/sha}","trees_url":"https://api.github.com/repos/denislos/mipt-mips/git/trees{/sha}","statuses_url":"https://api.github.com/repos/denislos/mipt-mips/statuses/{sha}","languages_url":"https://api.github.com/repos/denislos/mipt-mips/languages","stargazers_url":"https://api.github.com/repos/denislos/mipt-mips/stargazers","contributors_url":"https://api.github.com/repos/denislos/mipt-mips/contributors","subscribers_url":"https://api.github.com/repos/denislos/mipt-mips/subscribers","subscription_url":"https://api.github.com/repos/denislos/mipt-mips/subscription","commits_url":"https://api.github.com/repos/denislos/mipt-mips/commits{/sha}","git_commits_url":"https://api.github.com/repos/denislos/mipt-mips/git/commits{/sha}","comments_url":"https://api.github.com/repos/denislos/mipt-mips/comments{/number}","issue_comment_url":"https://api.github.com/repos/denislos/mipt-mips/issues/comments{/number}","contents_url":"https://api.github.com/repos/denislos/mipt-mips/contents/{+path}","compare_url":"https://api.github.com/repos/denislos/mipt-mips/compare/{base}...{head}","merges_url":"https://api.github.com/repos/denislos/mipt-mips/merges","archive_url":"https://api.github.com/repos/denislos/mipt-mips/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/denislos/mipt-mips/downloads","issues_url":"https://api.github.com/repos/denislos/mipt-mips/issues{/number}","pulls_url":"https://api.github.com/repos/denislos/mipt-mips/pulls{/number}","milestones_url":"https://api.github.com/repos/denislos/mipt-mips/milestones{/number}","notifications_url":"https://api.github.com/repos/denislos/mipt-mips/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/denislos/mipt-mips/labels{/name}","releases_url":"https://api.github.com/repos/denislos/mipt-mips/releases{/id}","deployments_url":"https://api.github.com/repos/denislos/mipt-mips/deployments","created_at":"2017-10-29T10:26:37Z","updated_at":"2017-10-29T10:26:38Z","pushed_at":"2017-12-05T16:31:17Z","git_url":"git://github.com/denislos/mipt-mips.git","ssh_url":"git@github.com:denislos/mipt-mips.git","clone_url":"https://github.com/denislos/mipt-mips.git","svn_url":"https://github.com/denislos/mipt-mips","homepage":"http://mipt-ilab.github.io/mipt-mips/","size":9885,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"other","name":"Other","spdx_id":null,"url":null},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"MIPT-ILab:master","ref":"master","sha":"83c58bb8c6e333f1e941154748ccf296ffd34b2b","user":{"login":"MIPT-ILab","id":13999586,"avatar_url":"https://avatars2.githubusercontent.com/u/13999586?v=4","gravatar_id":"","url":"https://api.github.com/users/MIPT-ILab","html_url":"https://github.com/MIPT-ILab","followers_url":"https://api.github.com/users/MIPT-ILab/followers","following_url":"https://api.github.com/users/MIPT-ILab/following{/other_user}","gists_url":"https://api.github.com/users/MIPT-ILab/gists{/gist_id}","starred_url":"https://api.github.com/users/MIPT-ILab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MIPT-ILab/subscriptions","organizations_url":"https://api.github.com/users/MIPT-ILab/orgs","repos_url":"https://api.github.com/users/MIPT-ILab/repos","events_url":"https://api.github.com/users/MIPT-ILab/events{/privacy}","received_events_url":"https://api.github.com/users/MIPT-ILab/received_events","type":"Organization","site_admin":false},"repo":{"id":42990634,"name":"mipt-mips","full_name":"MIPT-ILab/mipt-mips","owner":{"login":"MIPT-ILab","id":13999586,"avatar_url":"https://avatars2.githubusercontent.com/u/13999586?v=4","gravatar_id":"","url":"https://api.github.com/users/MIPT-ILab","html_url":"https://github.com/MIPT-ILab","followers_url":"https://api.github.com/users/MIPT-ILab/followers","following_url":"https://api.github.com/users/MIPT-ILab/following{/other_user}","gists_url":"https://api.github.com/users/MIPT-ILab/gists{/gist_id}","starred_url":"https://api.github.com/users/MIPT-ILab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MIPT-ILab/subscriptions","organizations_url":"https://api.github.com/users/MIPT-ILab/orgs","repos_url":"https://api.github.com/users/MIPT-ILab/repos","events_url":"https://api.github.com/users/MIPT-ILab/events{/privacy}","received_events_url":"https://api.github.com/users/MIPT-ILab/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/MIPT-ILab/mipt-mips","description":"Cycle-accurate pre-silicon simulator of MIPS CPU","fork":false,"url":"https://api.github.com/repos/MIPT-ILab/mipt-mips","forks_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/forks","keys_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/keys{/key_id}","collaborators_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/teams","hooks_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/hooks","issue_events_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/events{/number}","events_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/events","assignees_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/assignees{/user}","branches_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/branches{/branch}","tags_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/tags","blobs_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/git/refs{/sha}","trees_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/git/trees{/sha}","statuses_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/statuses/{sha}","languages_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/languages","stargazers_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/stargazers","contributors_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/contributors","subscribers_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/subscribers","subscription_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/subscription","commits_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/commits{/sha}","git_commits_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/git/commits{/sha}","comments_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/comments{/number}","issue_comment_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/comments{/number}","contents_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/contents/{+path}","compare_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/compare/{base}...{head}","merges_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/merges","archive_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/downloads","issues_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues{/number}","pulls_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls{/number}","milestones_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/milestones{/number}","notifications_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/labels{/name}","releases_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/releases{/id}","deployments_url":"https://api.github.com/repos/MIPT-ILab/mipt-mips/deployments","created_at":"2015-09-23T09:12:26Z","updated_at":"2017-12-02T13:45:17Z","pushed_at":"2017-12-05T16:31:19Z","git_url":"git://github.com/MIPT-ILab/mipt-mips.git","ssh_url":"git@github.com:MIPT-ILab/mipt-mips.git","clone_url":"https://github.com/MIPT-ILab/mipt-mips.git","svn_url":"https://github.com/MIPT-ILab/mipt-mips","homepage":"http://mipt-ilab.github.io/mipt-mips/","size":114876,"stargazers_count":23,"watchers_count":23,"language":"C++","has_issues":true,"has_projects":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":44,"mirror_url":null,"archived":false,"open_issues_count":35,"license":{"key":"other","name":"Other","spdx_id":null,"url":null},"forks":44,"open_issues":35,"watchers":23,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257"},"html":{"href":"https://github.com/MIPT-ILab/mipt-mips/pull/257"},"issue":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/257"},"comments":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/issues/257/comments"},"review_comments":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257/comments"},"review_comment":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/pulls/257/commits"},"statuses":{"href":"https://api.github.com/repos/MIPT-ILab/mipt-mips/statuses/f906c737dfe17f39a64c2fa9732ee690369fdb3b"}},"author_association":"COLLABORATOR"}}
{"actor":{"display_login":"pavelkryukov"}}