kamil-tarnas / bitarray Goto Github PK
View Code? Open in Web Editor NEWElastic implementation of bit array data structure
License: GNU General Public License v2.0
Elastic implementation of bit array data structure
License: GNU General Public License v2.0
Hijack helper objects and analyze theirs layout - they should be smaller - at least according to my common sense. Investigate why they are the size that they are.
Size of ElemRefHelper object tested seems to be really big for an object holding only one unsigned and one unsigned reference value. Check the layout of this object.
sizeof(ElemRefHelper) = 16
Does it?
Introduce compress function of some type, that can be applied to BitArray instance.
Mask used to truncate assigned value is static for a template instance. It can be calculated once, per class template instantiation.
The thing to consider is the data locality of such solution. It won't be any surprise if calculating mask each time, on the fly, in function call would be cheaper than the access to static storage data segment.
There is more optimal way to pack value elements in words that will make the calculation of padding bits unnecessary. Do more in-depth analysis and opportunity analysis for this change.
Current implementation considers only truncation of assigned values in order to be "safe". Consider implementing exception throwing instead.
Yeah, yeah, I know ;)
There is a need to be able to subscript BitArray instance variable and assign the return value to any integer-type variable:
Code snippet:
BitArray<10, 2> arrayObject;
int a = arrayObject[2];
Solution:
This would require BitArray::operator int() or some other integer type.
Open problems:
Modifying subscripted element would require modifying underlying storage, ElemRefHelper should contain pointer or reference to specific word of underlying storage to be able to modify it when demanded.
Code snippet:
BitArray<10, 2> arrayObject;
arrayObject[6] = 2;
Solution:
Converting constructor with integer type argument has to be implemented.
Open problems:
unsigned or char, if the latter - signed or unsigned?
Decide internal type for storage.
Self-explanatory pretty much.
Make a use of non-standard extensions, like attribute((packed)), attribute((aligned)) to make the allocations even more compact?
As the title says, maybe it would be beneficial to have a template parameter which could control the underlying type for internal storage. Appropriate default value should be implemented.
With C++17 CTAD the "<>" in case of dynamic BitArray object instantiation could be omitted. For the prior standards typedef or using could be implemented.
class BitArray<> is probably not a template partial specialization.
The parameter pack on the top of hierarchy of BitArray template is probably not needed?
The template could just omit the unused parameters in case of dynamic?
The BitArray first parameter pack does not need to be unsigned?
Move BitArray top declaration from utils.h to BitArray.h
All the problems stem from the fact that the above points were not clear back then?
Attach diagrams with descriptions to the repository.
Unnecessary copying of ElemRefHelper objects - objects are made in internal ElemRefHelper and BitArray implementation. It involves copies being made while switching from BitArray::operator[] creates an object of ElemRefHelper and then in operator unsigned() object of different address is being processed.
Document the layout of internal storage as cavemanjaw always forgets it.
Problem with static constexpr BitArray member vars - the variables seem to be uninitialized.
Investigate possibilities of wrapping code for getting and setting value of BitArray elements - the current situation is that there is a lot of code duplication. To be more precise, code differs slightly between those uses, so it could not be simply wrapped in some function.
How could it be made?
Replace CHAR_BITS with standard CHAR_BIT. Anything more lightweight than ?
What can be decided in compile time for dynamic array? Size of the element?
Decouple BitArray and gtest. Move BitArray to new, independent test environment, which would be more trivial. Lots of features of gtest are not needed at this point.
Merge local 'exceptions' branch to mimic 'master'
0b14f82 HEAD@{0}: commit: Removing duplicated line
8c60cb7 HEAD@{1}: rebase finished: returning to refs/heads/exceptions
8c60cb7 HEAD@{2}: rebase: Adding basic testcase to exceptions
256d226 HEAD@{3}: rebase: Adding unnecessary comment to throwing exception code
010c07c HEAD@{4}: rebase: Adding basic throwing if value in Set() is greater than possible bit resolution
aabafcb HEAD@{5}: rebase: Moving mask calculations to compile time, making mask variable static constexpr class template variable
db36cc6 HEAD@{6}: rebase: Adding comments for throwing during Set()
a38a16f HEAD@{7}: rebase: checkout master
dd16759 HEAD@{8}: checkout: moving from master to exceptions
a38a16f HEAD@{9}: checkout: moving from exceptions to master
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.