{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:38Z","timestamp":1740123878432,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,23]],"date-time":"2024-03-23T00:00:00Z","timestamp":1711152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,23]],"date-time":"2024-03-23T00:00:00Z","timestamp":1711152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["LA\/P\/0063\/2020"],"award-info":[{"award-number":["LA\/P\/0063\/2020"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006752","name":"Universidade do Porto","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006752","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Prolog systems rely on an atom table for symbol management, which is usually implemented as a dynamically resizeable hash table. This is ideal for single threaded execution, but can become a bottleneck in a multi-threaded scenario. In this work, we replace the original atom table implementation in the YAP Prolog system with a lock-free hash-based data structure, named Lock-free Hash Tries (LFHT), in order to provide efficient and scalable symbol management. Being lock-free, the new implementation also provides better guarantees, namely, immunity to priority inversion, to deadlocks and to livelocks. Performance results show that the new lock-free LFHT implementation has better results in single threaded execution and much better scalability than the original lock based dynamically resizing hash table.<\/jats:p>","DOI":"10.1007\/s10766-024-00766-z","type":"journal-article","created":{"date-parts":[[2024,3,23]],"date-time":"2024-03-23T07:10:03Z","timestamp":1711177803000},"page":"187-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Yet Another Lock-Free Atom Table Design for Scalable Symbol Management in Prolog"],"prefix":"10.1007","volume":"52","author":[{"given":"Pedro","family":"Moreno","sequence":"first","affiliation":[]},{"given":"Miguel","family":"Areias","sequence":"additional","affiliation":[]},{"given":"Ricardo","family":"Rocha","sequence":"additional","affiliation":[]},{"given":"V\u00edtor","family":"Santos Costa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,23]]},"reference":[{"key":"766_CR1","doi-asserted-by":"crossref","unstructured":"Areias, M., Rocha, R.: On the correctness and efficiency of lock-free expandable tries for tabled logic programs. In: International Symposium on Practical Aspects of Declarative Languages, no. 8324 in LNCS, pp. 168\u2013183. Springer (2014)","DOI":"10.1007\/978-3-319-04132-2_12"},{"issue":"3","key":"766_CR2","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/s10766-014-0346-1","volume":"44","author":"M Areias","year":"2016","unstructured":"Areias, M., Rocha, R.: A lock-free hash trie design for concurrent tabled logic programs. Int. J. Parallel Prog. 44(3), 386\u2013406 (2016)","journal-title":"Int. J. Parallel Prog."},{"key":"766_CR3","doi-asserted-by":"crossref","unstructured":"Areias, M., Rocha, R.: Towards a lock-free, fixed size and persistent hash map design. In: M.\u00a0Valero, A.\u00a0Melo (eds.) Proceedings of the International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2017), pp. 145\u2013152. IEEE Computer Society, Campinas, Brazil (2017)","DOI":"10.1109\/SBAC-PAD.2017.26"},{"key":"766_CR4","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.jpdc.2021.01.001","volume":"150","author":"M Areias","year":"2021","unstructured":"Areias, M., Rocha, R.: On the correctness and efficiency of a novel lock-free hash trie map design. J. Parallel Distrib. Comput. 150, 184\u2013195 (2021). https:\/\/doi.org\/10.1016\/j.jpdc.2021.01.001","journal-title":"J. Parallel Distrib. Comput."},{"key":"766_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-022-01085-2","author":"M Areias","year":"2022","unstructured":"Areias, M., Rocha, R.: On the correctness of a lock-free compression-based elastic mechanism for a hash trie design. Computing (2022). https:\/\/doi.org\/10.1007\/s00607-022-01085-2","journal-title":"Computing"},{"key":"766_CR6","unstructured":"Bagwell, P.: Ideal hash trees. Es Grands Champs 1195 (2001)"},{"key":"766_CR7","doi-asserted-by":"crossref","unstructured":"Benton, W.C., Fischer, C.N.: Interactive, scalable, declarative program analysis: from prototype to implementation. In: Leuschel, M., Podelski, A. (eds.) Proceedings of the 9th international ACM SIGPLAN conference on principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland, pp. 13\u201324. ACM (2007)","DOI":"10.1145\/1273920.1273923"},{"key":"766_CR8","unstructured":"Devitt, S., Roo, J.D., Chen, H.: Desirable features of rule based systems for medical knowledge. In: W3C workshop on rule languages for interoperability, 27\u201328 April 2005, Washington, DC, USA. W3C (2005)"},{"key":"766_CR9","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E Fredkin","year":"1962","unstructured":"Fredkin, E.: Trie Memory. Commun. ACM 3, 490\u2013499 (1962)","journal-title":"Commun. ACM"},{"key":"766_CR10","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/11871842_20","volume-title":"Machine Learning: ECML 2006","author":"B Gutmann","year":"2006","unstructured":"Gutmann, B., Kersting, K.: Tildecrf: Conditional random fields for logical sequences. In: F\u00fcrnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) Machine Learning: ECML 2006, pp. 174\u2013185. Springer, Berlin Heidelberg (2006)"},{"key":"766_CR11","first-page":"458","volume-title":"Proceedings of the 26th International European Conference on Parallel and Distributed Computing (Euro-Par 2020), LNCS","author":"P Moreno","year":"2020","unstructured":"Moreno, P., Areias, M., Rocha, R.: A compression-based design for higher throughput in a lock-free hash map. In: Malawski, M., Rzadca, K. (eds.) Proceedings of the 26th International European Conference on Parallel and Distributed Computing (Euro-Par 2020), LNCS, pp. 458\u2013473. Springer International Publishing, Warsaw, Poland (2020)"},{"key":"766_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jpdc.2021.04.007","volume":"155","author":"P Moreno","year":"2021","unstructured":"Moreno, P., Areias, M., Rocha, R.: On the implementation of memory reclamation methods in a lock-free hash trie design. J. Parallel Distrib. Comput. 155, 1\u201313 (2021). https:\/\/doi.org\/10.1016\/j.jpdc.2021.04.007","journal-title":"J. Parallel Distrib. Comput."},{"key":"766_CR13","unstructured":"Moura, P.: ISO\/IEC DTR 13211\u20135:2007 prolog multi-threading predicates (2008). http:\/\/logtalk.org\/plstd\/threads.pdf"},{"key":"766_CR14","first-page":"1","volume-title":"Logic Programming, 25th International Conference, ICLP 2009, Pasadena, CA, USA, July 14-17, 2009. Proceedings, Lecture Notes in Computer Science","author":"C Mungall","year":"2009","unstructured":"Mungall, C.: Experiences using logic programming in bioinformatics. In: Hill, P.M., Warren, D.S. (eds.) Logic Programming, 25th International Conference, ICLP 2009, Pasadena, CA, USA, July 14-17, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5649, pp. 1\u201321. Springer, Berlin (2009)"},{"key":"766_CR15","volume-title":"An Introduction to Language Processing with Perl and Prolog: An Outline of Theories, Implementation, and Application with Special Consideration of English, French, and German (Cognitive Technologies)","author":"PM Nugues","year":"2006","unstructured":"Nugues, P.M.: An Introduction to Language Processing with Perl and Prolog: An Outline of Theories, Implementation, and Application with Special Consideration of English, French, and German (Cognitive Technologies). Springer-Verlag, New York Inc (2006)"},{"key":"766_CR16","first-page":"415","volume":"4","author":"D Page","year":"2003","unstructured":"Page, D., Srinivasan, A.: Ilp: a short look back and a longer look forward. J. Mach. Learn. Res. 4, 415\u2013430 (2003)","journal-title":"J. Mach. Learn. Res."},{"key":"766_CR17","doi-asserted-by":"crossref","unstructured":"Prokopec, A., Bronson, N.G., Bagwell, P., Odersky, M.: Concurrent tries with efficient non-blocking snapshots. In: ACM Symposium on Principles and Practice of Parallel Programming, pp. 151\u2013160. ACM (2012)","DOI":"10.1145\/2370036.2145836"},{"key":"766_CR18","unstructured":"Santos Costa, V.: On supporting parallelism in a logic programming system. In: Workshop on Declarative Aspects of Multicore Programming, pp. 77\u201391 (2008)"},{"issue":"1 & 2","key":"766_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1017\/S1471068411000512","volume":"12","author":"V Santos Costa","year":"2012","unstructured":"Santos Costa, V., Rocha, R., Damas, L.: The YAP prolog system. J. Theory Pract. Logic Program. 12(1 & 2), 5\u201334 (2012)","journal-title":"J. Theory Pract. Logic Program."},{"key":"766_CR20","first-page":"305","volume-title":"Proceedings of the 23rd International Conference on Logic Programming, Lecture Notes in Computer Science","author":"V Santos Costa","year":"2007","unstructured":"Santos Costa, V., Sagonas, K., Lopes, R.: Demand-driven indexing of prolog clauses. In: Dahl, V., Niemel\u00e4, I. (eds.) Proceedings of the 23rd International Conference on Logic Programming, Lecture Notes in Computer Science, vol. 4670, pp. 305\u2013409. Springer, Berlin (2007)"},{"issue":"3","key":"766_CR21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/1147954.1147958","volume":"53","author":"O Shalev","year":"2006","unstructured":"Shalev, O., Shavit, N.: Split-ordered lists: lock-free extensible hash tables. J. ACM 53(3), 379\u2013405 (2006)","journal-title":"J. ACM"},{"key":"766_CR22","unstructured":"Srinivasan, A.: The aleph manual (2004). http:\/\/www.cs.ox.ac.uk\/activities\/machlearn\/Aleph"},{"key":"766_CR23","unstructured":"Triplett, J., McKenney, P.E., Walpole, J.: Resizable, scalable, concurrent hash tables via relativistic programming. In: USENIX Annual Technical Conference, p.\u00a011. USENIX Association (2011)"},{"key":"766_CR24","unstructured":"Warren, D.H.D.: An abstract prolog instruction set. Technical Note 309, SRI International (1983)"},{"key":"766_CR25","doi-asserted-by":"crossref","unstructured":"Wielemaker, J.: Native preemptive threads in SWI-prolog. In: International Conference on Logic Programming, no. 2916 in LNCS, pp. 331\u2013345. Springer (2003)","DOI":"10.1007\/978-3-540-24599-5_23"},{"issue":"5\u20136","key":"766_CR26","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1017\/S1471068416000272","volume":"16","author":"J Wielemaker","year":"2016","unstructured":"Wielemaker, J., Harris, K.: Lock-free atom garbage collection for multithreaded prolog. Theory Pract. Logic Program. 16(5\u20136), 950\u2013965 (2016)","journal-title":"Theory Pract. Logic Program."}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00766-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-024-00766-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00766-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T15:33:55Z","timestamp":1718638435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-024-00766-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,23]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["766"],"URL":"https:\/\/doi.org\/10.1007\/s10766-024-00766-z","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[2024,3,23]]},"assertion":[{"value":"16 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}