Skip to content

Instantly share code, notes, and snippets.

@cloudwu
Created December 16, 2020 08:22
Show Gist options
  • Save cloudwu/7eca0a00d7f877c6093b081cab588015 to your computer and use it in GitHub Desktop.
Save cloudwu/7eca0a00d7f877c6093b081cab588015 to your computer and use it in GitHub Desktop.
#ifndef lazy_memory_h
#define lazy_memory_h
#include <stdint.h>
#include <string.h>
#define CacheLine 64
#define WordSize (sizeof(uint64_t) * 8) // 64 (bits)
#define AlignN(s, n) (( s + n - 1) / n * n)
#define AlignCacheLine(s) AlignN(s, CacheLine)
#define LazyMemorySize AlignCacheLine(LazyMemoryCount * sizeof(LazyMemoryType))
#define LazyMemorySegment (LazyMemorySize / CacheLine)
#define LazyMemoryCacheSize ((LazyMemorySegment + WordSize - 1) / WordSize)
#define LazyMemoryCacheSegment ((LazyMemoryCacheSize + WordSize - 1)/ WordSize)
struct LazyMemoryCache {
uint64_t buffer[AlignN(LazyMemoryCacheSize, LazyMemoryCacheSegment)];
uint64_t cache;
};
struct LazyMemory {
uint8_t buffer[LazyMemorySize];
struct LazyMemoryCache cache;
};
static inline void
LazyMemoryCacheInit(struct LazyMemoryCache *c) {
c->cache = 0;
}
static inline uint64_t
LazyMemoryCacheIndex(struct LazyMemoryCache *c, unsigned int index) {
unsigned int segment = index / LazyMemoryCacheSegment;
uint64_t mask = (uint64_t)1 << segment;
if (c->cache & mask) {
return c->buffer[index];
} else {
memset(c->buffer + segment * LazyMemoryCacheSegment, 0, LazyMemoryCacheSegment * sizeof(uint64_t));
c->cache |= mask;
return 0;
}
}
static inline void
LazyMemoryInit(struct LazyMemory *m) {
LazyMemoryCacheInit(&m->cache);
}
static inline LazyMemoryType*
LazyMemoryIndex(struct LazyMemory *m, unsigned int object_index) {
unsigned int index = object_index * sizeof(LazyMemoryType);
unsigned int segment_index = index / CacheLine;
unsigned int cache_index = segment_index / WordSize;
uint64_t cache = LazyMemoryCacheIndex(&m->cache, cache_index);
uint64_t mask = (uint64_t)1 << (segment_index - cache_index * WordSize);
if ((cache & mask) == 0) {
memset(m->buffer + segment_index * CacheLine, 0, CacheLine);
m->cache.buffer[cache_index] = cache | mask;
}
return (LazyMemoryType*)&m->buffer[index];
}
#endif
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
struct SPathSearchValue
{
int32_t m_f;
int32_t m_g;
};
#define MAX_PATH_SEARCH_GRID_RANGE 200
#define MAX_LAYER_COUNT 16
#define LazyMemoryType struct SPathSearchValue
#define LazyMemoryCount (MAX_PATH_SEARCH_GRID_RANGE*MAX_PATH_SEARCH_GRID_RANGE*MAX_LAYER_COUNT)
#include "lazymemory.h"
struct SPathSearchValue *
get(struct LazyMemory *m, unsigned int x, unsigned int y, unsigned int layer) {
unsigned int index = (x * MAX_PATH_SEARCH_GRID_RANGE + y) * MAX_LAYER_COUNT + layer;
return LazyMemoryIndex(m, index);
}
// sizeof struct LazyMemory is huge, don't use it on stack
struct LazyMemory *
init() {
struct LazyMemory * mem = (struct LazyMemory *)malloc(sizeof(struct LazyMemory));
LazyMemoryInit(mem);
return mem;
}
void
test(struct LazyMemory *mem) {
struct SPathSearchValue *v;
int i,j,layer;
for (i=0;i<MAX_PATH_SEARCH_GRID_RANGE;i++) {
for (j=0;j<MAX_PATH_SEARCH_GRID_RANGE;j++) {
for (layer=0;layer<MAX_LAYER_COUNT;layer++) {
v = get(mem, i,j,layer);
if (v->m_f != 0 || v->m_g != 0) {
printf("Invalid %d %d %d %u %u\n", i,j,layer, v->m_f, v->m_g);
exit(1);
}
v->m_f = i;
v->m_g = j;
}
}
}
for (i=0;i<MAX_PATH_SEARCH_GRID_RANGE;i++) {
for (j=0;j<MAX_PATH_SEARCH_GRID_RANGE;j++) {
for (layer=0;layer<MAX_LAYER_COUNT;layer++) {
v = get(mem, i,j,layer);
if (v->m_f != i || v->m_g != j) {
printf("Invalid2 %d %d %d %u %u\n", i,j,layer, v->m_f, v->m_g);
exit(1);
}
}
}
}
}
int
main() {
// sizeof struct LazyMemory is huge, don't use it on stack
struct LazyMemory *mem = (struct LazyMemory *)malloc(sizeof(*mem));
memset(mem, 1, sizeof(*mem));
LazyMemoryInit(mem);
free(mem);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment