uncp / aili Goto Github PK
View Code? Open in Web Editor NEWthe fastest in-memory index in the East 东半球最快并发索引
License: BSD 3-Clause "New" or "Revised" License
the fastest in-memory index in the East 东半球最快并发索引
License: BSD 3-Clause "New" or "Revised" License
ArtNode256结点孩子数可能为0到256,用8bit表示count值刚好表示不下吧?
如题,可以解释一下mapping_array在b-link tree实现过程中的目的和意义吗,非常感谢。
另外作者是否可以给我一个您的邮箱,想问您一些未来工作选择的问题,再次感谢。
rt
我把线程数提高到8偶尔会卡死,提高到64一动不动
https://github.com/UncP/aili/blob/master/art/art_node.c#L395
这里是不是写错了? add_child 增加节点应该是往 children pointers 的末尾append一个 node. 所以不应该是 an48->child[get_count(version)] = child;
才对吧?
Hi! First of all, congratulations for the performance achieved on your implementation!
I would like to know if you plan to implement the delete operation on your Multi ART algorithm.
根据专栏文章 https://zhuanlan.zhihu.com/p/52624601 提供的伪代码,
uint32_t before = node_get_stable_version(n);
// read node here
uint32_t after = node_get_version(n); // no need to be stable, just latest version
if ((before ^ after == LOCK_BIT) || (before ^ after == 0))
// neither insert nor split happened
acquire 保证之后的读操作不会重排至当前操作之前, 但不保证之前的读操作不重排至当前操作之后, 换言之, after 的值可能比 read node 过程中的值从全局时间线来看更早.
实际运行有没有可能是这样的?
uint32_t before = node_get_stable_version(n);
uint32_t after = node_get_version(n); // no need to be stable, just latest version
// read node here
// WE HAVE A BIG PROBLEM NOW
if ((before ^ after == LOCK_BIT) || (before ^ after == 0))
// neither insert nor split happened
是不是用 memory_order_seq_cst 更安全一点?
X86 保证 load load 不乱序, 只要编译器不重排是没有问题的.
请问插入的时候,为什么不会发生这样的情况:
树的各个节点均已满,一个线程P企图插入,它下降到了某个叶节点,此时另外几个线程也开始插入,它们下降了不同的叶节点然后插入结束,导致旧root分裂,新root生成,并且导致旧root所在那一层再次满了,这时线程P向上回溯,回溯到旧root后依然要进行分裂,可是线程P并不知道旧root的parent(也就是新root)是谁。
您的代码中,下面这行代码
Line 133 in a2f3225
Lines 124 to 127 in a2f3225
====================[ Build | aili | Debug ]====================================
/home/muxin/devTool/clion-2019.2.5/bin/cmake/linux/bin/cmake --build /home/muxin/IdeaProjects/aili/cmake-build-debug --target aili -- -j 4
Scanning dependencies of target aili
[ 3%] Building C object CMakeFiles/aili.dir/palm/metric.c.o
[ 6%] Building C object CMakeFiles/aili.dir/test/art_test.c.o
[ 9%] Building C object CMakeFiles/aili.dir/test/mass_node_test.c.o
[ 12%] Building C object CMakeFiles/aili.dir/test/mass_tree_test.c.o
/home/muxin/IdeaProjects/aili/palm/metric.c:12:10: fatal error: c_hashmap/hashmap.h: No such file or directory
#include <c_hashmap/hashmap.h>
^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
CMakeFiles/aili.dir/build.make:257: recipe for target 'CMakeFiles/aili.dir/palm/metric.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/palm/metric.c.o] Error 1
make[3]: *** Waiting for unfinished jobs....
/home/muxin/IdeaProjects/aili/test/mass_node_test.c:14:10: fatal error: ../mass/node.h: No such file or directory
#include "../mass/node.h"
^~~~~~~~~~~~~~~~
compilation terminated.
/home/muxin/IdeaProjects/aili/test/art_test.c: In function ‘test_adaptive_radix_tree_structure’:
/home/muxin/IdeaProjects/aili/test/art_test.c:171:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key1, 5, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:172:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key2, 6, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:173:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key3, 7, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:197:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key1, 7, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:198:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key2, 6, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:199:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key3, 5, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
CMakeFiles/aili.dir/build.make:335: recipe for target 'CMakeFiles/aili.dir/test/mass_node_test.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/test/mass_node_test.c.o] Error 1
CMakeFiles/aili.dir/build.make:309: recipe for target 'CMakeFiles/aili.dir/test/art_test.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/test/art_test.c.o] Error 1
/home/muxin/IdeaProjects/aili/test/mass_tree_test.c: In function ‘test_mass_tree’:
/home/muxin/IdeaProjects/aili/test/mass_tree_test.c:135:3: warning: implicit declaration of function ‘mass_tree_validate’; did you mean ‘mass_tree_get’? [-Wimplicit-function-declaration]
mass_tree_validate(mt);
^~~~~~~~~~~~~~~~~~
mass_tree_get
CMakeFiles/Makefile2:75: recipe for target 'CMakeFiles/aili.dir/all' failed
make[2]: *** [CMakeFiles/aili.dir/all] Error 2
CMakeFiles/Makefile2:82: recipe for target 'CMakeFiles/aili.dir/rule' failed
make[1]: *** [CMakeFiles/aili.dir/rule] Error 2
Makefile:118: recipe for target 'aili' failed
make: *** [aili] Error 2
Lines 261 to 293 in a2f3225
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.