Felipe97/llama-cpp-compiled
01.1k
1#include "ggml.h"2#include "llama.h"3 4#ifdef NDEBUG5#undef NDEBUG6#endif7 8#include <algorithm>9#include <cmath>10#include <cstdlib>11#include <string>12#include <vector>13 14extern struct llama_sampler * llama_sampler_init_dry_testing(float dry_multiplier, float dry_base, int32_t dry_allowed_length, int32_t dry_penalty_last_n, const std::vector<std::vector<llama_token>>& seq_breakers);15 16static void dump(const llama_token_data_array * cur_p) {17 for (size_t i = 0; i < cur_p->size; i++) {18 printf("%d: %f (%f)\n", cur_p->data[i].id, cur_p->data[i].p, cur_p->data[i].logit);19 }20}21 22#define DUMP(__cur_p) do { printf("%s:%d (%s)\n", __FILE__, __LINE__, __func__); dump((__cur_p)); printf("-\n"); } while(0)23 24struct sampler_tester {25 sampler_tester(size_t n_vocab) {26 cur.reserve(n_vocab);27 for (llama_token token_id = 0; token_id < (llama_token)n_vocab; token_id++) {28 const float logit = logf(token_id);29 cur.emplace_back(llama_token_data{token_id, logit, 0.0f});30 }31 32 cur_p = llama_token_data_array { cur.data(), cur.size(), -1, false };33 }34 35 sampler_tester(const std::vector<float> & probs, const std::vector<float> & probs_expected) : probs_expected(probs_expected) {36 cur.reserve(probs.size());37 for (llama_token token_id = 0; token_id < (llama_token)probs.size(); token_id++) {38 const float logit = logf(probs[token_id]);39 cur.emplace_back(llama_token_data{token_id, logit, probs[token_id]});40 }41 42 cur_p = llama_token_data_array { cur.data(), cur.size(), -1, false };43 }44 45 void apply(llama_sampler * sampler) {46 llama_sampler_apply(sampler, &cur_p);47 llama_sampler_free(sampler);48 }49 50 void check() {51 GGML_ASSERT(cur_p.size == probs_expected.size());52 for (size_t i = 0; i < cur_p.size; i++) {53 GGML_ASSERT(fabs(cur_p.data[i].p - probs_expected[i]) < 1e-5);54 }55 }56 57 llama_token_data_array cur_p;58 59private:60 const std::vector<float> probs_expected;61 62 std::vector<llama_token_data> cur;63};64 65static llama_token sample_dist(llama_sampler * sampler, const std::vector<float> & logits) {66 std::vector<llama_token_data> cur;67 for (llama_token token_id = 0; token_id < (llama_token) logits.size(); ++token_id) {68 cur.push_back({ token_id, logits[token_id], 0.0f });69 }70 71 llama_token_data_array cur_p = { cur.data(), cur.size(), -1, false };72 llama_sampler_apply(sampler, &cur_p);73 GGML_ASSERT(cur_p.selected >= 0);74 GGML_ASSERT((size_t) cur_p.selected < cur_p.size);75 return cur_p.data[cur_p.selected].id;76}77 78static void test_dist_singleton_rng() {79 llama_sampler * singleton = llama_sampler_init_dist(4242);80 llama_sampler * control = llama_sampler_init_dist(4242);81 82 sample_dist(singleton, { 0.0f });83 sample_dist(control, { 0.0f, 0.0f });84 85 const std::vector<float> logits(256, 0.0f);86 for (int i = 0; i < 4; ++i) {87 GGML_ASSERT(sample_dist(singleton, logits) == sample_dist(control, logits));88 }89 90 llama_sampler_free(singleton);91 llama_sampler_free(control);92}93 94static void test_temp(const std::vector<float> & probs, const std::vector<float> & probs_expected, float temp) {95 sampler_tester tester(probs, probs_expected);96 97 DUMP(&tester.cur_p);98 tester.apply(llama_sampler_init_temp(temp));99 tester.apply(llama_sampler_init_dist(0));100 DUMP(&tester.cur_p);101 102 tester.check();103}104 105static void test_temp_ext(const std::vector<float> & probs, const std::vector<float> & probs_expected, float temp, float delta, float exponent) {106 sampler_tester tester(probs, probs_expected);107 108 DUMP(&tester.cur_p);109 tester.apply(llama_sampler_init_temp_ext(temp, delta, exponent));110 tester.apply(llama_sampler_init_dist (0));111 DUMP(&tester.cur_p);112 113 tester.check();114}115 116static void test_top_k(const std::vector<float> & probs, const std::vector<float> & probs_expected, int k) {117 sampler_tester tester(probs, probs_expected);118 119 DUMP(&tester.cur_p);120 tester.apply(llama_sampler_init_top_k(k));121 tester.apply(llama_sampler_init_dist (0));122 DUMP(&tester.cur_p);123 124 tester.check();125}126 127static void test_top_p(const std::vector<float> & probs, const std::vector<float> & probs_expected, float p) {128 sampler_tester tester(probs, probs_expected);129 130 DUMP(&tester.cur_p);131 tester.apply(llama_sampler_init_top_p(p, 0));132 tester.apply(llama_sampler_init_dist (0));133 DUMP(&tester.cur_p);134 135 tester.check();136}137 138static void test_min_p(const std::vector<float> & probs, const std::vector<float> & probs_expected, float p) {139 sampler_tester tester(probs, probs_expected);140 141 DUMP(&tester.cur_p);142 tester.apply(llama_sampler_init_min_p(p, 0));143 tester.apply(llama_sampler_init_dist (0));144 DUMP(&tester.cur_p);145 146 tester.check();147}148 149static void test_xtc(const std::vector<float> & probs, const std::vector<float> & probs_expected, float p, float t) {150 sampler_tester tester(probs, probs_expected);151 152 DUMP(&tester.cur_p);153 tester.apply(llama_sampler_init_xtc(p, t, 0, 0));154 DUMP(&tester.cur_p);155 156 tester.check();157}158 159static void test_typical(const std::vector<float> & probs, const std::vector<float> & probs_expected, float p) {160 sampler_tester tester(probs, probs_expected);161 162 DUMP(&tester.cur_p);163 tester.apply(llama_sampler_init_typical(p, 0));164 DUMP(&tester.cur_p);165 166 tester.check();167}168 169static void test_penalties(170 const std::vector<float> & probs, const std::vector<llama_token> & last_tokens,171 const std::vector<float> & probs_expected, float repeat_penalty, float alpha_frequency, float alpha_presence172) {173 GGML_ASSERT(probs.size() == probs_expected.size());174 175 sampler_tester tester(probs, probs_expected);176 177 auto * sampler = llama_sampler_init_penalties((int32_t) probs.size(), (int32_t) last_tokens.size(), repeat_penalty, alpha_frequency, alpha_presence);178 179 for (size_t i = 0; i < last_tokens.size(); i++) {180 llama_sampler_accept(sampler, last_tokens[i]);181 }182 183 DUMP(&tester.cur_p);184 tester.apply(sampler);185 tester.apply(llama_sampler_init_dist(0));186 DUMP(&tester.cur_p);187 188 tester.check();189}190 191static void test_dry(192 const std::vector<float> & probs, const std::vector<llama_token> & last_tokens,193 const std::vector<float> & expected_probs, float dry_multiplier, float dry_base,194 int dry_allowed_length, int dry_penalty_last_n,195 const std::vector<std::vector<llama_token>> & seq_breakers196) {197 GGML_ASSERT(probs.size() == expected_probs.size());198 199 sampler_tester tester(probs, expected_probs);200 201 auto * sampler = llama_sampler_init_dry_testing(dry_multiplier, dry_base, dry_allowed_length, dry_penalty_last_n, seq_breakers);202 203 for (size_t i = 0; i < last_tokens.size(); i++) {204 llama_sampler_accept(sampler, last_tokens[i]);205 }206 207 DUMP(&tester.cur_p);208 tester.apply(sampler);209 tester.apply(llama_sampler_init_dist(0));210 DUMP(&tester.cur_p);211 tester.check();212}213 214static void test_top_n_sigma(const std::vector<float> & probs, const std::vector<float> & probs_expected, int n) {215 sampler_tester tester(probs, probs_expected);216 217 DUMP(&tester.cur_p);218 tester.apply(llama_sampler_init_top_n_sigma(n));219 tester.apply(llama_sampler_init_dist (0));220 DUMP(&tester.cur_p);221 222 tester.check();223}224 225static void test_sampler_queue(const size_t n_vocab, const std::string & samplers_sequence, const int top_k, const float top_p, const float min_p226) {227 sampler_tester tester(n_vocab);228 229 llama_token min_token_id = 0;230 const llama_token max_token_id = n_vocab - 1;231 232 for (auto s : samplers_sequence) {233 switch (s) {234 case 'k': tester.apply(llama_sampler_init_top_k(top_k)); break;235 case 'y': GGML_ABORT("typical test not implemented");236 case 'p': tester.apply(llama_sampler_init_top_p(top_p, 1)); break;237 case 'm': tester.apply(llama_sampler_init_min_p(min_p, 1)); break;238 case 't': GGML_ABORT("temperature test not implemented");239 default : GGML_ABORT("Unknown sampler");240 }241 242 tester.apply(llama_sampler_init_dist(0));243 244 auto & cur_p = tester.cur_p;245 246 const int size = cur_p.size;247 248 if (s == 'k') {249 const int expected_size = std::min(size, top_k);250 min_token_id = std::max(min_token_id, (llama_token)(n_vocab - top_k));251 252 GGML_ASSERT(size == expected_size);253 GGML_ASSERT(cur_p.data[0].id == max_token_id);254 GGML_ASSERT(cur_p.data[expected_size-1].id == min_token_id);255 } else if (s == 'p') {256 const int softmax_divisor = n_vocab * (n_vocab-1) / 2 - min_token_id * (min_token_id-1) / 2;257 const int softmax_numerator_target = ceilf(top_p * softmax_divisor);258 259 min_token_id = n_vocab;260 int expected_size = 0;261 int cumsum = 0;262 do { // do-while because always at least one token is sampled263 min_token_id--;264 expected_size++;265 266 cumsum += min_token_id;267 } while (cumsum < softmax_numerator_target);268 269 // token 0 has p == 0, need special consideration for cumsum because top_p immediately returns270 if (min_token_id == 1) {271 min_token_id--;272 expected_size += 1;273 }274 275 GGML_ASSERT(size == expected_size);276 GGML_ASSERT(!cur_p.sorted || cur_p.data[0].id == max_token_id);277 GGML_ASSERT(!cur_p.sorted || cur_p.data[expected_size-1].id == min_token_id);278 } else if (s == 'm') {279 int expected_size = ceilf((1.0f - min_p) * n_vocab);280 expected_size = std::max(expected_size, 1);281 expected_size = std::min(expected_size, size);282 283 min_token_id = floorf(min_p * n_vocab);284 min_token_id = std::max(min_token_id, 1);285 min_token_id = std::max(min_token_id, (llama_token)(n_vocab - size));286 min_token_id = std::min(min_token_id, (llama_token)(n_vocab - 1));287 288 GGML_ASSERT(size == expected_size);289 GGML_ASSERT(!cur_p.sorted || cur_p.data[0].id == max_token_id);290 GGML_ASSERT(!cur_p.sorted || cur_p.data[expected_size-1].id == min_token_id);291 } else {292 GGML_ABORT("fatal error");293 }294 }295 296 printf("Sampler queue %3s OK with n_vocab=%05zu top_k=%5d top_p=%f min_p=%f\n",297 samplers_sequence.c_str(), n_vocab, top_k, top_p, min_p);298}299 300static void bench(llama_sampler * cnstr, const char * cnstr_name, const std::vector<llama_token_data> & data, int n_iter) {301 std::vector<llama_token_data> cur(data.size());302 std::copy(data.begin(), data.end(), cur.begin());303 llama_token_data_array cur_p = { cur.data(), cur.size(), -1, false };304 llama_sampler_apply(cnstr, &cur_p);305 llama_sampler_reset(cnstr);306 const int64_t t_start = ggml_time_us();307 for (int i = 0; i < n_iter; i++) {308 std::copy(data.begin(), data.end(), cur.begin());309 llama_token_data_array cur_p = { cur.data(), cur.size(), -1, false };310 llama_sampler_apply(cnstr, &cur_p);311 llama_sampler_reset(cnstr);312 }313 const int64_t t_end = ggml_time_us();314 llama_sampler_free(cnstr);315 printf("%-43s: %8.3f us/iter\n", cnstr_name, (t_end - t_start) / (float)n_iter);316}317 318#define BENCH(__cnstr, __data, __n_iter) bench((__cnstr), #__cnstr, (__data), (__n_iter))319 320static void test_perf() {321 const int n_vocab = 1 << 17;322 323 std::vector<llama_token_data> data;324 325 data.reserve(n_vocab);326 for (int i = 0; i < n_vocab; i++) {327 const float logit = 2.0f*((double)(rand())/RAND_MAX - 0.5);328 data.emplace_back(llama_token_data{i, logit, 0.0f});329 }330 331 BENCH(llama_sampler_init_top_k (40), data, 32);332 BENCH(llama_sampler_init_top_p (0.8f, 1), data, 32);333 BENCH(llama_sampler_init_min_p (0.2f, 1), data, 32);334 BENCH(llama_sampler_init_typical(0.5f, 1), data, 32);335 BENCH(llama_sampler_init_xtc (1.0f, 0.1f, 1, 1), data, 32);336}337 338int main(void) {339 ggml_time_init();340 341 test_dist_singleton_rng();342 343 test_temp({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 1.0f);344 test_temp({0.1f, 0.2f, 0.3f, 0.4f}, {0.0f, 0.0f, 0.0f, 1.0f}, 0.0f);345 346 test_temp_ext({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 1.0f, 0.0f, 1.0f);347 test_temp_ext({0.1f, 0.2f, 0.3f, 0.4f}, {0.0f, 0.0f, 0.0f, 1.0f}, 0.0f, 0.0f, 1.0f);348 349 test_top_k({0.1f, 0.2f, 0.3f, 0.4f}, {1.0f}, 1);350 test_top_k({0.1f, 0.2f, 0.3f, 0.4f}, {0.44444f, 0.33333f, 0.22222f}, 3);351 test_top_k({0.1f, 0.2f, 0.3f, 0.4f}, {0.4f, 0.3f, 0.2f, 0.1f}, 4);352 test_top_k({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 0);353 354 test_top_p({0.1f, 0.2f, 0.3f, 0.4f}, {1.0f}, 0);355 test_top_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.571429f, 0.428571f}, 0.7f);356 test_top_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.44444f, 0.33333f, 0.22222f}, 0.8f);357 test_top_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 1.0f);358 359 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f/1.0f, 0.2f/1.0f, 0.3f/1.0f, 0.4f/1.0f}, 0.00f);360 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f/1.0f, 0.2f/1.0f, 0.3f/1.0f, 0.4f/1.0f}, 0.24f);361 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.2f/0.9f, 0.3f/0.9f, 0.4f/0.9f}, 0.26f);362 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.2f/0.9f, 0.3f/0.9f, 0.4f/0.9f}, 0.49f);363 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.3f/0.7f, 0.4f/0.7f}, 0.51f);364 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.3f/0.7f, 0.4f/0.7f}, 0.74f);365 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.4f/0.4f}, 0.76f);366 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.4f/0.4f}, 1.00f);367 test_min_p({0.1f, 0.2f, 0.3f, 0.4f}, {0.4f/0.4f}, 1.05f);368 369 printf("XTC should:\n");370 test_xtc({0.4f, 0.3f, 0.2f, 0.1f}, {0.1f}, 0.99f, 0.09f);371 test_xtc({0.4f, 0.3f, 0.2f, 0.1f}, {0.2f, 0.1f}, 0.99f, 0.19f);372 test_xtc({0.4f, 0.3f, 0.2f, 0.1f}, {0.3f, 0.2f, 0.1f}, 0.99f, 0.29f);373 374 printf("XTC should not:\n");375 test_xtc({0.4f, 0.3f, 0.2f, 0.1f}, {0.4f, 0.3f, 0.2f, 0.1f}, 0.99f, 0.39f);376 377 test_typical({0.97f, 0.01f, 0.01f, 0.01f}, {0.97f}, 0.5f);378 test_typical({0.4f, 0.2f, 0.2f, 0.2f}, {0.2f, 0.2f, 0.2f}, 0.5f);379 380 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0}, {0, 0.25f, 0.25f, 0.25f, 0.25f}, 50.0f, 0.0f, 0.0f);381 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2}, {0, 0, 0, 0.5f, 0.5f}, 50.0f, 0.0f, 0.0f);382 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2, 0, 0}, {0, 0, 0, 0.5f, 0.5f}, 50.0f, 0.0f, 0.0f);383 384 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0}, {0.000011f, 0.249997f, 0.249997f, 0.249997f, 0.249997f}, 1.0f, 5.0f, 5.0f);385 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2}, {0.000023f, 0.000023f, 0.000023f, 0.499966f, 0.499966f}, 1.0f, 5.0f, 5.0f);386 test_penalties({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2, 0, 0}, {0.000000f, 0.000023f, 0.000023f, 0.499977f, 0.499977f}, 1.0f, 5.0f, 5.0f);387 388 389 test_dry({0.25f, 0.25f, 0.25f, 0.25f}, {0, 1}, {0.25f, 0.25f, 0.25f, 0.25f}, 1.0f, 1.1f, 2, 4, {});390 test_dry({0.25f, 0.25f, 0.25f, 0.25f}, {0, 1, 2, 0, 1}, {0.296923f, 0.296923f, 0.109232f, 0.296923f}, 1.0f, 1.1f, 2, 5, {});391 test_dry({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 3, 4, 0, 1}, {0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, 1.0f, 1.1f, 2, 6, {{3}});392 test_dry({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2, 0, 1}, {0.241818f, 0.241818f, 0.032727f, 0.241818f, 0.241818f}, 2.0f, 1.1f, 2, 5, {});393 test_dry({0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, {0, 1, 2, 3, 4, 0, 1}, {0.2f, 0.2f, 0.2f, 0.2f, 0.2f}, 1.0f, 1.1f, 4, 7, {});394 395 test_top_n_sigma({0.1f, 0.2f, 0.3f, 0.4f}, {0.0f, 0.0f, 0.428571f, 0.571429f}, 1.00f);396 test_top_n_sigma({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 0.00f); // top_n_sigma == 0 now represents a no-op rather than greedy decoding as of PR#13345397 test_top_n_sigma({0.1f, 0.2f, 0.3f, 0.4f}, {0.1f, 0.2f, 0.3f, 0.4f}, 3.00f);398 399 test_sampler_queue(10000, "k", 10000, 1.0f, 1.0f);400 test_sampler_queue(10000, "k", 1, 1.0f, 1.0f);401 test_sampler_queue(10000, "p", 10000, 1.0f, 1.0f);402 test_sampler_queue(10000, "p", 10000, 0.0f, 1.0f);403 test_sampler_queue(10000, "m", 10000, 1.0f, 1.0f);404 test_sampler_queue(10000, "m", 10000, 1.0f, 1e-12);405 406 test_sampler_queue(10000, "k", 100, 1.0000f, 1.0f);407 test_sampler_queue(10000, "p", 10000, 0.0003f, 1.0f);408 test_sampler_queue(10000, "p", 10000, 0.8000f, 1.0f);409 test_sampler_queue(10000, "m", 10000, 1.0000f, 9997.9f/9999.0f);410 test_sampler_queue(10000, "m", 10000, 1.0000f, 0.1f);411 412 test_sampler_queue(10000, "kp", 100, 0.8f, 0.1f);413 test_sampler_queue(10000, "km", 100, 0.8f, 0.1f);414 test_sampler_queue(10000, "pk", 100, 0.8f, 0.1f);415 test_sampler_queue(10000, "pm", 100, 0.8f, 0.1f);416 test_sampler_queue(10000, "mk", 100, 0.8f, 0.1f);417 test_sampler_queue(10000, "mp", 100, 0.8f, 9997.9f/9999.0f);418 test_sampler_queue(10000, "mp", 100, 0.8f, 0.1f);419 420 test_sampler_queue(10000, "kpm", 100, 0.8f, 0.1f);421 test_sampler_queue(10000, "kmp", 100, 0.8f, 0.1f);422 test_sampler_queue(10000, "pkm", 100, 0.8f, 0.1f);423 test_sampler_queue(10000, "pmk", 100, 0.8f, 0.1f);424 test_sampler_queue(10000, "mkp", 100, 0.8f, 0.1f);425 test_sampler_queue(10000, "mpk", 100, 0.8f, 0.1f);426 427 printf("OK\n");428 429 test_perf();430 431 return 0;432}433