Brunobkr/llama.cpp_AlgMor24_github

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