fork download
copy 
  1. // static best-fit allocator utilizing std::multimap.
  2. // @ingroup experimental
  3.  
  4. #include <algorithm>
  5. #include <cassert>
  6. #include <map>
  7.  
  8. // @internal
  9. // memory block header size in words.
  10. #define HEADER_SIZE static_cast<word_type>(1)
  11.  
  12. // @internal
  13. // extract block size from block header.
  14. #define BLOCK_SIZE(location) \
  15. 	(heap[(location) - HEADER_SIZE])
  16.  
  17. // heap types/members.
  18. typedef unsigned int word_type;
  19. constexpr  word_type heap_size = 1000000;
  20. word_type  heap[heap_size];
  21.  
  22. // key: block size; data: block location.
  23. std::multimap<word_type, word_type> free_list;
  24.  
  25. void heap_initialize()
  26. {
  27. 	word_type next = HEADER_SIZE;
  28. 	BLOCK_SIZE(next) = heap_size;
  29. 	extern void release(word_type);
  30. 	release(next);
  31. }
  32.  
  33. void release(word_type p)
  34. {
  35. 	if (p != 0)
  36. 		free_list.insert(std::make_pair(BLOCK_SIZE(p), p));
  37. }
  38.  
  39. word_type acquire(word_type request)
  40. {
  41. 	if (request == 0)
  42. 		return 0;
  43.  
  44. 	// threshold minimum is (header + 1*data word).
  45. 	word_type threshold = 8;
  46. 	request = (request + HEADER_SIZE + (threshold-1))
  47. 			/ threshold * threshold;
  48.  
  49. 	// locate best-fit.
  50. 	auto best_iter = free_list.lower_bound(request);
  51.  
  52. 	// no suitable block found.
  53. 	if (best_iter == free_list.end())
  54. 		throw std::bad_alloc();
  55.  
  56. 	// extract index; update free list.
  57. 	word_type best = best_iter->second;
  58. 	free_list.erase(best_iter);
  59.  
  60. 	// split block.
  61. 	if (BLOCK_SIZE(best) > request + threshold) {
  62. 		word_type  next  = best + request;
  63. 		BLOCK_SIZE(next) = BLOCK_SIZE(best) - request;
  64. 		BLOCK_SIZE(best) = request;
  65. 		release(next);
  66. 	}
  67. 	return best;
  68. }
  69.  
  70. // TESTING
  71. #include <iostream>
  72. #include <sstream>
  73. #include <memory>
  74. #include <random>
  75. #include <chrono>
  76. #include <thread>
  77. #include <mutex>
  78. #include <vector>
  79. #include <cstring>
  80.  
  81. // extract pointer from index.
  82. // @note since heap memory is static we don't need to worry
  83. // about pointer invalidation.
  84. #define BLOCK_PTR(location) \
  85. 	(& heap[(location)])
  86.  
  87. void thread_out(int id, const char* stage)
  88. {
  89. 	std::stringstream ss;
  90. 	ss << "pid(" << id << "): " << stage << '\n';
  91. 	std::cout << ss.str();
  92. }
  93.  
  94. void spastic_alloc(int id, int count, int size, long* total_allocated)
  95. {
  96. 	// hopefully this is obnoxious enough to crash if something is wrong.
  97. 	std::default_random_engine random(std::random_device().operator()());
  98. 	auto garbage = std::make_unique<word_type[]>(size);
  99. 	std::generate(garbage.get(), garbage.get() + size, random);
  100.  
  101. 	// this randomization is an attempt to increase the likelyhood
  102. 	// acquire and release are interleaved.
  103. 	int msectick = std::uniform_int_distribution<>(0, 250)(random);
  104. 	std::this_thread::sleep_for(std::chrono::milliseconds(msectick));
  105. 	int allocations = std::uniform_int_distribution<>(count/8, count)(random);
  106. 	// first: address; second: size.
  107. 	std::vector<std::pair<word_type, word_type>> result(allocations);
  108.  
  109. 	static std::mutex mutex;
  110. 	thread_out(id, "acquire");
  111. 	for ( auto& p : result ) {
  112. 		p.second = std::uniform_int_distribution<>(1, size)(random);
  113. 		*total_allocated += p.second;
  114. 		// the allocator is not thread safe so we hold the lock while
  115. 		// acquire is active.
  116. 		{
  117. 			std::lock_guard<std::mutex> lock(mutex);
  118. 			p.first = acquire(p.second);
  119. 		}
  120. 		std::copy(garbage.get(), garbage.get() + p.second,
  121. 				BLOCK_PTR(p.first));
  122. 	}
  123.  
  124. 	std::shuffle(result.begin(), result.end(), random);
  125. 	thread_out(id, "release");
  126. 	for ( auto p : result ) {
  127. 		assert(std::equal(garbage.get(), garbage.get() + p.second,
  128. 				BLOCK_PTR(p.first)));
  129. 		std::memset(BLOCK_PTR(p.first), 0xA5, p.second * sizeof(word_type));
  130. 		// same deal here.
  131. 		std::lock_guard<std::mutex> lock(mutex);
  132. 		release(p.first);
  133. 	}
  134. }
  135.  
  136. int main(int argc, char* argv[])
  137. {
  138. 	heap_initialize();
  139.  
  140. 	int thread_count = 4;
  141. 	std::vector<std::thread> threads;
  142.  
  143. 	long total_allocated = 0;
  144. 	for ( int i = 0; i < thread_count; i++ )
  145. 		threads.emplace_back(spastic_alloc, i, 500, 1024, &total_allocated);
  146. 	for ( auto& thread : threads )
  147. 		thread.join();
  148.  
  149. 	std::cout << "Total words allocated: " << total_allocated << '\n';
  150. 	std::cout << "Free block count: " << free_list.size() << '\n';
  151. 	return 0;
  152. }
Success #stdin #stdout 0s 19672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
pid(0): acquire
pid(0): release
pid(2): acquire
pid(2): release
pid(3): acquire
pid(3): release
pid(1): acquire
pid(1): release
Total words allocated: 781746
Free block count: 688
https://ideone.com/ePsMsw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!