Blog

// heap.hpp — glibc mallinfo2()로 현재 사용 중인 힙 바이트를 잰다
#pragma once
#include <malloc.h>

// uordblks: brk 영역에서 사용 중, hblkhd: mmap으로 받은 큰 블록
inline std::size_t heap_in_use()
{
	struct mallinfo2 mi = mallinfo2();
	return mi.uordblks + mi.hblkhd;
}

// naive.cpp — 글자마다 서식 전체를 들고 있는 문서
#include <iostream>
#include <string>
#include <vector>
#include "heap.hpp"

struct Glyph {
	char ch;
	int x, y;                                    // 위치: 글자마다 다르다
	std::string font;                            // 서식: 대부분 같다
	int size;
	std::string color;
};

int main()
{
	const std::size_t base = heap_in_use();
	const int N = 100000;
	const char *fonts[] = {"Noto Sans KR Regular", "Noto Sans KR Bold", "D2Coding Ligature"};
	std::vector<Glyph> doc;
	doc.reserve(N);
	for (int i = 0; i < N; ++i)
		doc.push_back({char('a' + i % 26), i % 80, i / 80, fonts[i % 3], 11, "#1f2328"});
	std::cout << "glyphs=" << doc.size() << " sizeof(Glyph)=" << sizeof(Glyph)
		  << " heap in use=" << (heap_in_use() - base) / 1024 << " KiB\n";
}

// flyweight.cpp — 공유 가능한 서식(내재 상태)은 풀에서 하나씩만, 위치(외재 상태)만 글자마다
#include <iostream>
#include <memory>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#include "heap.hpp"

struct Style {                                   // Flyweight: 불변, 공유됨
	std::string font;
	int size;
	std::string color;
};

class StyleFactory {                             // FlyweightFactory
public:
	const Style *get(const std::string &font, int size, const std::string &color)
	{
		std::string key = font + '|' + std::to_string(size) + '|' + color;
		auto [it, inserted] = pool_.try_emplace(key, nullptr);
		if (inserted)
			it->second = std::make_unique<const Style>(Style{font, size, color});
		return it->second.get();
	}
	std::size_t count() const { return pool_.size(); }
private:
	std::unordered_map<std::string, std::unique_ptr<const Style>> pool_;
};

struct Glyph {
	char ch;
	int x, y;
	const Style *style;                          // 공유 서식을 가리키기만 한다
};

int main()
{
	const std::size_t base = heap_in_use();
	const int N = 100000;
	const char *fonts[] = {"Noto Sans KR Regular", "Noto Sans KR Bold", "D2Coding Ligature"};
	StyleFactory styles;
	std::vector<Glyph> doc;
	doc.reserve(N);
	for (int i = 0; i < N; ++i)
		doc.push_back({char('a' + i % 26), i % 80, i / 80, styles.get(fonts[i % 3], 11, "#1f2328")});
	std::cout << "glyphs=" << doc.size() << " sizeof(Glyph)=" << sizeof(Glyph)
		  << " styles=" << styles.count()
		  << " heap in use=" << (heap_in_use() - base) / 1024 << " KiB\n";
	std::cout << "glyph[0] and glyph[3] share style: " << std::boolalpha
		  << (doc[0].style == doc[3].style) << '\n';
}

// weak_cache.cpp — 아무도 안 쓰는 플라이웨이트는 자동으로 풀에서 빠지게(weak_ptr)
#include <iostream>
#include <map>
#include <memory>
#include <string>

struct Texture {
	std::string path;
	explicit Texture(std::string p) : path(std::move(p)) { std::cout << "  load " << path << '\n'; }
	~Texture() { std::cout << "  unload " << path << '\n'; }
};

class TextureCache {
public:
	std::shared_ptr<const Texture> get(const std::string &path)
	{
		if (auto alive = cache_[path].lock())        // 살아 있으면 공유
			return alive;
		auto t = std::make_shared<const Texture>(path);
		cache_[path] = t;                             // 풀은 소유하지 않는다
		return t;
	}
	std::size_t alive() const
	{
		std::size_t n = 0;
		for (const auto &[k, w] : cache_)
			n += !w.expired();
		return n;
	}
private:
	std::map<std::string, std::weak_ptr<const Texture>> cache_;
};

int main()
{
	TextureCache cache;
	{
		auto a = cache.get("grass.png");
		auto b = cache.get("grass.png");          // 다시 로드하지 않음
		auto c = cache.get("stone.png");
		std::cout << "same object: " << std::boolalpha << (a == b)
			  << ", use_count=" << a.use_count() << ", alive=" << cache.alive() << '\n';
	}                                                  // 모든 사용자가 사라짐
	std::cout << "after scope alive=" << cache.alive() << '\n';
	auto d = cache.get("grass.png");                   // 필요해지면 다시 로드
}

// intern.cpp — 문자열 인터닝: 같은 내용은 같은 주소 → 비교가 포인터 비교가 된다
#include <chrono>
#include <iostream>
#include <string>
#include <string_view>
#include <unordered_set>
#include <vector>

class Interner {
public:
	std::string_view intern(std::string_view s) { return *pool_.emplace(s).first; }
	std::size_t size() const { return pool_.size(); }
private:
	std::unordered_set<std::string> pool_;          // 노드 기반이라 원소 주소가 안정적
};

int main()
{
	Interner in;
	std::vector<std::string_view> tags;
	// 길이가 같고 앞부분 27바이트가 같은 문자열: 내용 비교는 그만큼 읽어야 다름을 안다
	const char *words[] = {"/sys/devices/system/cpu/cpu0/cpufreq/scaling_governor",
			       "/sys/devices/system/cpu/cpu1/cpufreq/scaling_governor",
			       "/sys/devices/system/cpu/cpu2/cpufreq/scaling_governor"};
	for (int i = 0; i < 300000; ++i)
		tags.push_back(in.intern(words[i % 3]));

	auto target = in.intern("/sys/devices/system/cpu/cpu2/cpufreq/scaling_governor");
	auto t0 = std::chrono::steady_clock::now();
	std::size_t by_ptr = 0;
	for (auto t : tags)
		by_ptr += t.data() == target.data();          // 주소 비교
	auto t1 = std::chrono::steady_clock::now();
	std::size_t by_str = 0;
	for (auto t : tags)
		by_str += t == target;                         // 내용 비교
	auto t2 = std::chrono::steady_clock::now();

	using us = std::chrono::microseconds;
	std::cout << "unique strings=" << in.size() << " handles=" << tags.size() << '\n'
		  << "pointer compare: " << by_ptr << " matches, "
		  << std::chrono::duration_cast<us>(t1 - t0).count() << " us\n"
		  << "content compare: " << by_str << " matches, "
		  << std::chrono::duration_cast<us>(t2 - t1).count() << " us\n";
}

/* intern.c — C 인턴 테이블: 같은 문자열은 같은 const char * 하나만 */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NBUCKET 64

struct entry { struct entry *next; char str[]; };   /* flexible array member */
static struct entry *buckets[NBUCKET];
static int g_unique;

static unsigned hash(const char *s)
{
	unsigned h = 2166136261u;                          /* FNV-1a */
	while (*s)
		h = (h ^ (unsigned char)*s++) * 16777619u;
	return h;
}

const char *intern(const char *s)
{
	unsigned b = hash(s) % NBUCKET;
	for (struct entry *e = buckets[b]; e; e = e->next)
		if (strcmp(e->str, s) == 0)
			return e->str;                     /* 이미 있으면 공유 */
	struct entry *e = malloc(sizeof(*e) + strlen(s) + 1);
	if (!e)
		abort();
	strcpy(e->str, s);
	e->next = buckets[b];
	buckets[b] = e;
	g_unique++;
	return e->str;
}

int main(void)
{
	char buf[32];
	const char *first = NULL, *p = NULL;

	for (int i = 0; i < 1000; i++) {
		snprintf(buf, sizeof(buf), "eth%d", i % 4);   /* 매번 새 버퍼의 내용 */
		p = intern(buf);
		if (i == 0)
			first = p;
	}
	printf("calls=1000 unique=%d\n", g_unique);
	printf("intern(\"eth0\") == first: %d\n", intern("eth0") == first);
	for (int b = 0; b < NBUCKET; b++)
		while (buckets[b]) {
			struct entry *n = buckets[b]->next;
			free(buckets[b]);
			buckets[b] = n;
		}
	return 0;
}