Implement lock-free queues in NIF

Questions / Help
,
1

I’m going to write a lock-free queue in nif. i want create a resource type that uses enif_alloc_env to allocate a global ErlNifEnv environment to store all enqueue ERL_NIF_TERM. But if you look at the NIF documentation, the storage ERL_NIF_TERM will not be released immediately after it is dequeue, unless the ErlNifEnv is released using enif_free_env or enif_clear_env. However, there may be other ERL_NIF_TERM needs to be used in the global ErlNifEnv, so can’t we do this? It seems inefficient to enif_alloc_env an ErlNifEnv to an enqueue ERL_NIF_TERM and enif_free_env to an ErlNifEnv when dequeue the ERL_NIF_TERM. Do you have any good suggestions?

3 Likes
2

No, you cannot deallocate a single term from an environment. If the terms you intend to send are big enough then the extra allocation of the environment will not matter all that much, but if the terms are small you may want to batch the operations.

For instance, you could allocate N terms to the same environment and then send a deallocation message on the queue.

Though if the terms are going to be sent to an Erlang process in the end anyway then you might as well create an environment as that is needed to send the message anyway.

3 Likes
3

Thank you for your answer. If so, I will try to create an additional ErlNifEnv cache queue and reuse the ErlNifEnv by call enif_clear_env after. let me implement it to test the performance.

2 Likes
4

I wrote the first version of the lock based on GitHub - cameron314/concurrentqueue: A fast multi-producer, multi-consumer lock-free concurrent queue for C++11 - free queue, and then I did some test, I went to the insert into the queue 1000000 integer, then spent more than 800 M of memory, Ets only needs tens of megabytes of memory to insert 1000000 {Num}, which is crazy. I gave up this implementation.

2 Likes
5

If you want to use less memory, then you might want to try to use enif_term_to_binary to not need an environment anymore. It will use a bit more CPU to encode/decode the term, but you will only have to allocate memory for the binary holding the encoded term. This is essentially what the compress option for ets does.

2 Likes
6

I’m quite curious why you’re needing to go the nif route?

2 Likes
7

I’ve done that, But not fast enough.

2 Likes
8

I used ETS to implement a FIFO but ETS does not support first_take last_take. I wanted a more perfect implementation. I thought NIF would be faster, but the test used too much memory. Then I have implemented ets:first_take ets:last_take. Just like this:

/*
** first_take(Tab, Key)
*/
BIF_RETTYPE ets_first_take_1(BIF_ALIST_1)
{
    DbTable* tb;
    int cret;
    Eterm first_key;
    Eterm ret;
    CHECK_TABLES();

    DB_BIF_GET_TABLE(tb, DB_WRITE, LCK_WRITE_REC, BIF_ets_take_2);

    cret = tb->common.meth->db_first(BIF_P, tb, &first_key);
    ASSERT(cret == DB_ERROR_NONE); (void)cret;

    cret = tb->common.meth->db_take(BIF_P, tb, first_key, &ret);
    ASSERT(cret == DB_ERROR_NONE); (void)cret;

    db_unlock(tb, LCK_WRITE_REC);
    BIF_RET(ret);
}

/*
** last_take(Tab, Key)
*/
BIF_RETTYPE ets_last_take_1(BIF_ALIST_1)
{
    DbTable* tb;
    int cret;
    Eterm last_key;
    Eterm ret;
    CHECK_TABLES();

    DB_BIF_GET_TABLE(tb, DB_WRITE, LCK_WRITE_REC, BIF_ets_take_2);

    cret = tb->common.meth->db_last(BIF_P, tb, &last_key);
    ASSERT(cret == DB_ERROR_NONE); (void)cret;

    cret = tb->common.meth->db_take(BIF_P, tb, last_key, &ret);
    ASSERT(cret == DB_ERROR_NONE); (void)cret;

    db_unlock(tb, LCK_WRITE_REC);
    BIF_RET(ret);
}

that’s the easiest way to do it. Maybe using bIF to implement lock-free queue would be less memory

3 Likes
9

Finally, I wrapped the lock-free queue with nif: GitHub - ErlGameWorld/eLfq: erlang's NIF Lock-Free Queue, And use in: GitHub - ErlGameWorld/eFaw: eralng's Factories and workers., It is faster than implementing FIFO queue using ETS.

2 Likes