Design cache tests

[chungphb]

No description provided.

[chungphb]

Test put

Consecutive data

If n_unique_items <= capacity

• Example:
  • Cache: capacity = 4
  • Access pattern: 1 2 3 (n_unique_items = 3)
  • Cache items / Cache history: {1}/{} -> {2 1}/{} -> {3 2 1}/{}
• Requirements:
  • Cache items = REVERSE({Access pattern})
  • Cache history = {}

If n_unique_items > capacity

• Example:
  • Cache: capacity = 4
  • Access pattern: 1 2 3 4 5 6 (n_unique_items = 6)
  • Cache items / Cache history: {1}/{} -> {2 1}/{} -> {3 2 1}/{} -> {4 3 2 1}/{} -> {5 4 3 2}/{1} -> {6 5 4 3}/{2 1}
• Requirements:
  • Cache items = GET_FIRST_N_ITEMS(REVERSE({Access pattern)), capacity)
  • Cache history != REVERSE(GET_FIRST_N_ITEMS({Access pattern}, n_unique_items - capacity))

Random data

If n_unique_items <= capacity

• Example:
  • Cache: capacity = 4
  • Access pattern: 1 3 2 4 4 2 1 3 (n_unique_items = 4)
  • Cache items / Cache history: {1}/{} -> {3 1}/{} -> {2 3 1}/{} -> {4 2 3 1}/{} -> {4 2 3 1}/{} -> {2 4 3 1}/{} -> {1 2 4 3}/{} -> {3 1 2 4}/{}
• Requirements:
  • Cache items = REMOVE_DUPLICATION(REVERSE({Access pattern}))
  • Cache history = {}

If n_unique_items > capacity

• Example:
  • Cache: capacity = 3
  • Access pattern: 1 3 2 4 4 2 1 3 (n_unique_items = 4)
  • Cache items / Cache history: {1}/{} -> {3 1}/{} -> {2 3 1}/{} -> {4 2 3}/{1} -> {4 2 3}/{1} -> {2 4 3}/{1} -> {1 2 4}/{3 1} -> {3 1 2}/{4 3 1}
• Requirements:
  • Cache items = GET_FIRST_N_ITEMS(REMOVE_DUPLICATION(REVERSE({Access pattern)), capacity)
  • Cache history != {} [TODO]

[chungphb]

Test get

• There is no need to differentiate consecutive access pattern and random access pattern because for the most part, n_unique_items on the "get" access pattern will be less than or equal to the cache size and the requirements for these two cases are fairly similar.
• For items not on the cache, we can check them separately to avoid complication.

If n_unique_items = size

• Example:
  • Cache (after putting): 1 2 3 4 (size = 4)
  • Access pattern: 1 3 2 4 2 3 (n_unique_items = 4)
  • Cache items: {1 2 3 4} -> {3 1 2 4} -> {2 3 1 4} -> {4 2 3 1} -> {2 4 3 1} -> {3 2 4 1}
• Requirements:
  • Cache items = REMOVE_DUPLICATION(REVERSE({Access pattern}))

If n_unique_items < size

• Example:
  • Cache (after putting): 1 2 3 4 (size = 4)
  • Access pattern: 1 3 1 1 3 (n_unique_items = 2)
  • Cache items: {1 2 3 4} -> {3 1 2 4} -> {1 3 2 4} -> {1 3 2 4} -> {3 1 2 4}
• Requirements:
  • GET_FIRST_N_ITEMS({Cache items}, n_unique_items) = REMOVE_DUPLICATION(REVERSE({Access pattern}))
  • This could also be applied for the first scenario.