Comments (22)
Hi there,
Thank you using sparsepp, and for for taking the time to report this issue. Indeed iterators may be invalidated when an item is inserted into sparsepp, and that is expected behavior, but I should have stated it clearly in the readme.md (which I will update).
Please note that inserting an item into a std::unordered_map may also invalidate iterators, albeit only if this causes a resize. As stated in the doc for std::unordered_map:
"If rehashing occurs due to the insertion, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count()."
Using the temp variable is a good solution. I think insert would also work as the parameters would be evaluated first:
map.insert({keyB, (*iter).second});
from sparsepp.
Ah ok, that makes sense. I was replacing unordered_map in some third-party code and it never occurred to me the existing code could be mis-using the STL.
Just by changing a few unordered_maps to sparse_hash_maps and fixing that insertion bug, I've managed to speed up our code by about 1.5x, and reduce our memory consumption by 20% as well, so thanks for that!
from sparsepp.
Well, the invalidation of iterators when inserting will occur more often with sparsepp, so I certainly should mention it in the readme. Really glad to hear that you are happy with sparsepp. Do you use it on windows or linux?
from sparsepp.
from sparsepp.
OK. Then you may want to watch for a new version in a couple weeks. I have noticed that on windows, the memory saving is not as good as it should be because the windows default allocator (malloc) fragments the heap and has a very high overhead... so I'm currently implementing a special allocator for sparsepp which will solve this issue. With that new version, the memory savings will be much higher on Windows, and on par with what is currently seen on linux.
from sparsepp.
Hi and thanks for sharing the code,
I wonder if there has been any progress on this:
I'm currently implementing a special allocator for sparsepp which will solve this issue. With that new
version, the memory savings will be much higher on Windows, and on par with what is currently seen
on linux
Thanks
Michael
from sparsepp.
Working on it. Sorry it is taking longer than I had forecast, there are lots of little details to get right. The allocator is working great. I'm now integrating it with sparsepp but that probably will still take a couple weeks.
from sparsepp.
@mlmsft , Just curious, are you using sparsepp already or is this for a future project?
from sparsepp.
We are experimenting with it as an alternative to unordered_map, which is a true memory hog. At the moment, we are observing about 20% improvement due to sparsepp, which is already good, but a bit behind original expectations. So,we are looking forward to see sparsepp Windows performance catching up with the Linux version. Incidentally, sparsepp is somewhat difficult to debug in VS, but it will be a small price to pay if it cuts memory requirements.
Thanks
Michael
from sparsepp.
Great, I think you'll be very pleased with the memory usage with the custom allocator. Why do you say it is difficult to debug in VS? Is it because the code is somewhat cryptic and hard to follow, or is there a specific issue? I myself debug it in VS all the time.
from sparsepp.
The issue with debugging I was talking about is how VS displays hash contents.
Attached is a snapshot showing contents of unordered_map and , below it, sparsepp:
In the first case, we see an associative array, in the second case, the view is a bit cryptic.
from sparsepp.
Oh, thanks for explaining the issue, clearly this is not helpful at all. I'll look into creating a natvis file, so that the debugger can display sparsepp objects in a more useful fashion. Hopefully it wont be too difficult.
from sparsepp.
Terrific. Looking forward to seeing all those changes in the library.
Thanks for being so responsive!
Michael
from sparsepp.
Hi Michael,
I just added a spp.natvis file which allows user-friendly visualization of sparse_hash_map/set. I Have tested it with Visual Studio 2015, but it may work for 2012/2013.
- just copy the spp.natvis file to %VSINSTALLDIR%\Common7\Packages\Debugger\Visualizers (requires admin access)
- or to My Documents\Visual Studio 2015\Visualizers\
- or just add the file to your project
from sparsepp.
Yes, visualization works exactly like the built-in implementation now. It might be a small addition, but probably very helpful for VS developers using your library.
I have VS 2015, just like you do, so I can only confirm that it works there.
Thank you!
Michael
from sparsepp.
You are welcome!
from sparsepp.
Hi Greg,
Any updates on memory allocator for Windows?
Thanks
Michael
from sparsepp.
I am still working on the memory allocator. One thing you could try is to download the file "malloc.c" from http://g.oswego.edu/dl/html/malloc.html, and just add it to your project. It is the excellent allocator by Doug Lea. I would be very curious to hear jow it impacts the memory usage of your app.
from sparsepp.
@mlmsft , just checked in the version with the new allocator. It is used by default on Windows.Give it a try and let me know what you think!
from sparsepp.
Hi Greg,
Thanks for checking in the update. I didn't get to see its performance yet, mostly due to compilation issues. Few things that caught my (and Visual Studio's) attention:
- You have
#define DEBUG 0
in spp_dlalloc.h which is likely to collide with preprocessor definitions, especially because many people use #ifdef to see if they are in debug mode. Maybe give the macro a different name? - There are many non-static functions that are also defined in this file. As a result, including the spp.h header file in several source files of a library/executable is problematic
- Unrelated to this, but in reference to a previous solved issue: how about expanding the natvis file to show not just the actual map but also associated iterators?
Best
Michael
from sparsepp.
Michael, thank you for the quick feedback!
- yes, I'll fix the DEBUG.
- I'll also check the non-static functions...
- natvis for iterators => will do
from sparsepp.
Hi @mlmsft , I just checked in a fix for the first two issues. Hopefully it will build for you now.
from sparsepp.
Related Issues (20)
- Support operator[] with rvalue HOT 1
- When hashing on vector HOT 13
- Help me to serialize/deserialize sparse_hash_map<int , vector< std::string > > HOT 1
- missing return value in function spp_sptr& operator=(spp_sptr &&o) ? HOT 1
- SIGSEGV on using move-assigned-from hash set HOT 3
- Unable to create map for value type with deleted copy constructor HOT 2
- Can't insert std::tuple: spp uses deleted constructor/destructor HOT 1
- Lookup non-present keys becomes very slow. HOT 1
- Do you support C++11 stateful allocators? HOT 1
- Default allocator doesn't throw and caller doesn't check for NULL HOT 1
- SEGV after moving hash_map HOT 2
- conan package HOT 2
- sparse_hash_map<uint32_t, uint64_t> takes more memory than sparse_hash_map<uint64_t, uint64_t> HOT 1
- memcpy can happen with null "source" parameter HOT 6
- class-memaccess warning when compiling with GCC 8 or later HOT 1
- Problem when compiling on macOS catalina HOT 6
- Can sparse_hash_map support unique_ptr?
- Compiler warning on realloc call within sparsepp. HOT 1
- Error when compile: is not a special member function which can be defaulted HOT 2
- Missing return value. HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from sparsepp.