14 ms·

SDSL – Succinct Data Structure Library for C++

79 points by vsbuffalo 11y ago

olistovell 11y ago
Very nice! Why did you choose GPLv3 instead of LGPLv3?
- matt4711 11y ago
  The library is very template heavy and thus most of the code is in the header files so I guess it wouldn't change much in this case? Additionally, we (the main authors) have lots of contributions from other researchers which we would ask for permission to the change the license (I think?).
  - vog 11y ago
    Also, using GPL for a library is often the better choice! Many people believe that GPL is for programs and LGPL for libraries - as if the "L" would stand for "Library". But that's wrong! This was never the intention. The "L" stands for "Lesser" and means less protection than GPL, for very special circumstances. According to FSF, you should use LGPL only for libraries that are competing with widely accepted proprietary libraries. For anything new and original, you should use GPL - to promote Free Software. "Why you shouldn't use the Lesser GPL for your next library" https://www.gnu.org/licenses/why-not-lgpl.en.html https://www.gnu.org/licenses/why-not-lgpl.en.html (I disagree with that article in one point: If you compete with pervasive software, use a simple license like ISC/MIT/BSD rather than LGPL, to promote their usage even more.)
    - matt4711 11y ago
      Thanks for clarifying this.
    - UK-AL 11y ago
      It makes the library unusable for anyone, but open source software. If you write any sort of software, and link against this library, boom all the code needs to be GPL'ed. I don't think that's a good thing for promoting a library's use. Most people will just not use the library, and leave a bad taste in there mouth rather than spread the use of GPL. If you want your library to popular don't use GPL. What happens is that someone else comes a long and creates a MIT version. Eventually it gets replaced with the MIT version.
      - vog 11y ago
        > It makes the library unusable for anyone, but open source software. Well, the author is free to dual-license it to propriertary software for some fee - if they want. > I don't think that's a good thing for promoting a library's use But it's a good thing for promoting Open Source! That's the tactic question here: Do you want to promote your name and your library, or do you want to encourage more people to open source their stuff? In general you achieve both, but the question is: Which aspect is more important to you? > If you want your library to popular don't use GPL. What happens is that someone else comes a long and creates a MIT version. See https://news.ycombinator.com/item?id=10158535 https://news.ycombinator.com/item?id=10158535
        jheriko 11y ago
        i don't buy the rhetoric at face value and i don't think it helps promote open source at all. at best its promoting one flavour of open source methodologies in an authoritarian way. not open source software in general... it does little itself to teach us why open source is good, but its easy to learn why GPL is bad and tar all of open source with the same brush. the MIT and BSD style licenses are open source, but not militant about it. they are doing much better work to promote open source software imo since people will actually use software that is distributed under them in large commercial projects without fear, meaning that open source libraries do actually get used a lot, which lets people learn their advantages first hand... i like your quote about this. that someone will come along and make an MIT version... :)
        belorn 11y ago
        I have a very different question when I chose license for my software. I ask if my software might end up being used in a product where someone could get sued for sharing software online. I would personally be fine with a new license that simply said "Be nice or don't use my software. You can't sue people who use or share this software. You can't apply for patents and sue people who are being creative and code. You can't stop people from understanding the software that they run on their own machine.". However I doubt many companies would prefer that over GPLv3 so it easier to just use a commonly understood license which Linux distributions understand and find legally acceptable.
    - brlcad 11y ago
      Wow, this is just wrong. The L originally did stand for Library but FSF/Stallman wanted to discourage its use, so it was renamed it to Lesser. LGPL was created to appease authors that didn't want license terms to propagate like GPL, exceptionally common with library and embedded codes. Alas, ignorant authors were also choosing LGPL simply because they were creating a library and FSF didn't like that trend. It was a completely political move to fit their agenda. See https://en.wikipedia.org/wiki/GNU_Lesser_General_Public_License#History https://en.wikipedia.org/wiki/GNU_Lesser_General_Public_Lice...
      - vog 11y ago
        Indeed, the "L" originally stood for "Library", but the FSF declared this to be a mistake as it didn't express their intent. So I think it is fair to say that "L" was never intended to stand for "Library", although it accidentally did for some time.
    - jheriko 11y ago
      > very special circumstances. my experience is that these 'special' circumstances are pretty much "you need to use it in a proprietary production environment" and "you don't want to stop people using your software". this is close to what the FSF say so I don't think i'm far off the mark... the problem with GPL imo is that it is manifestly not free. you must abide by severe restrictions to use the code, which for a lot of software development would incur impractical costs. even if i want people to use my code for free I never use the full GPL license. i don't see any good reason to becasue i never want to dictate what other people can or can't do with their own software by virtue of having helped them out with mine. i really don't understand the sentiment... for example, the choice of GPL here means that nowhere i have ever worked would touch this officially. i can tell you that most of those places are also not thorough enough to stop some random wannabe hotshot programmer from stealing large swathes of code from this repo and using them anyway... (i do not endorse this practice - but i am perhaps a little bitter because i am usually the one who spots these things and has to deal with them).
      - belorn 11y ago
        If you want to define free as "do what you want" then feel free to do so but don't expect everyone to agree with it. I for example live in a free country but I am far from free to do what ever I want. The word "free" has in that single sentence two different definitions, which is why the word liberty is better. But to address one aspect, I do agree that I really don't understand the sentiment to dictate what other people can or can't do with their own software. Suing people for sharing software is wrong, and having EULA's that prevent people from understanding how their software operates is also wrong. The argument that you have to add proprietary licenses in order to earn a living is illogical and only create a world where people don't trust each other.
        jheriko 11y ago
        i think you have conflated some political rhetoric with reality there. free means free. its an abstract ideal... you do not live in a country where people are free, 'free country' and 'liberty' are politically charged terms which evoke particular ideals, which don't directly map to the meaning of the word 'freedom'. a big part of society is that we willingly give up certain freedoms for the greater good - this is what law is all about. in this particular case i think its clear cut. the GPL stops software from being free compared to an MIT or BSD style license...
  - justin66 11y ago
    >The library is very template heavy and thus most of the code is in the header files so I guess it wouldn't change much in this case? Pretty sure the end user is still required to gpl their project if they use your header files. edit: the more I think about this, the sadder I get. You prevented the majority of people from including your software and it doesn't sound like you meant to do it. Might be worth a rethink in the next version.
    - amelius 11y ago
      In spite of its good intentions, a restrictive license such as the GPL is always a weakness and a flaw. I would like to pose the conjecture that any library with a GPL license will eventually be replaced by a library with a more liberal license; the reason is simply because it has one feature extra, which is the more liberal license.
      - vog 11y ago
        > any library with a GPL license will eventually be replaced with a library with a more liberal license That's probably true, but it is not an argument against using the GPL. If your GPL library is original and useful, the cost of reimplementing it will probably higher than the cost of making some depending piece of software Open Source. So during the time until somebody else wrote that ISC/MIT/BSD version (which may be decades, think of GCC versus clang!), lots of other software may have been made Free Software that would otherwise have been proprietary.
        deleted 11y ago
        [deleted]
        jeffreyrogers 11y ago
        gcc vs. clang is probably a special case. Code compiled with gcc doesn't become GPL, which is part of why it is so popular.
        brlcad 11y ago
        I love open source and appreciate free software tenants, but think this is absolutely an argument against using the GPL for library-style codes. Your point is an ancillary benefit. Most authors don't publish libraries to encourage the greater FSF-ecosystem or free software agenda -- they publish to make it available to others and see it get put to use. Picking a license that limits prevalence of use is contrary to that objective, plain and simple. It also does not necessarily follow that proprietary would have been the alternative to free software. Published as ISC/MIT/BSD, lots of additional open source software would have been able to make use of the library, advanced more quickly, more easily permitted additional open source and free software derivatives, etc. More power to authors that choose to use GPL on a library code, as they are certainly entitled to do so, but it is a substantially limiting factor in the near and long term. We do not have to agree on these points. ;)
  - brlcad 11y ago
    It would absolutely change. GPL defines any incorporation or usage of a GPL work as a derivative work, thus effectively only permitting other GPL codes to use this library. That means any software in the Apache, Eclipse, or BSD-style ecosystems (among many others) cannot use this. As for multiple authors, in theory you were required to have their permission to release it under the GPL (or any other open source license) in the first place. Given your uncertainty, it's possible that permission wasn't obtained and you could already be on unstable legal ground. I would reach out to all contributors and ask them for permission to release under a more flexible license like BSD/MIT or Apache2 to encourage more widespread use.
- ioquatix 11y ago
  Why not the MIT or BSD license? It would be more useful for other developers.
  - KqAmJQ7 11y ago
    Quiet, Richard Stallman might hear you!
  - vog 11y ago
    I beg to differ. I'm always happy to use external GPL libraries as an excuse for making stuff Open Source. Whenever I talked to unsure customers or managers, this was the single most convincing argument. Of course, this only works if people aren't strictly against creating Free Software, but in that case you have lost anyway.
    - qznc 11y ago
      So you actively use the viral aspect of the GPL to make more stuff Open Source. Probably what Stallman intended. :)
      - vog 11y ago
        > Probably what Stallman intended. Probably? Is is exactly what he intended and what he asks the community to do. :-)
lorenzhs 11y ago
The SDSL is very easy to use, and its versatility is quite amazing. It's also rather interesting to look at the list of papers that cite it: https://scholar.google.com/scholar?cites=6772708594529960585 https://scholar.google.com/scholar?cites=6772708594529960585 and https://scholar.google.com/scholar?q=SDSL-lite https://scholar.google.com/scholar?q=SDSL-lite
amelius 11y ago
How does it compare in terms of memory and speed, to the GNU implementation of STL?
jbandela1 11y ago
Cool library. Any thoughts on getting it to work with Visual C++ 2015. It now has pretty decent C++11 support, you already use CMake, and this library seems like something that is inherently OS neutral. Even when I am ultimately deploying on Linux, I will often develop and debug my os-independent logic using Visual C++ on Windows and then when that is working well, recompile using g++ or clang++.
- matt4711 11y ago
  We are working on VS support. Last time we tried to port to VS some of the constexpr stuff we use was not available yet. The next release (in 1-2 month) should have full VS2015 support.
  - kjs3 11y ago
    Um...is that legal? Nothing in VS is licensed GPLv3.
jheriko 11y ago
this looks very cool but it is a shame about the license and a shame about the code style. STL is a poor exemplar to follow - its a real wasteland of a library and very deficient compared to libraries for other modern languages. however i will now go and learn these things and reinvent some wheels to make myself a better programmer. thanks. :)

79 points by vsbuffalo 11y ago

olistovell 11y ago

Very nice! Why did you choose GPLv3 instead of LGPLv3?

matt4711 11y ago
The library is very template heavy and thus most of the code is in the header files so I guess it wouldn't change much in this case? Additionally, we (the main authors) have lots of contributions from other researchers which we would ask for permission to the change the license (I think?).
- vog 11y ago
  Also, using GPL for a library is often the better choice! Many people believe that GPL is for programs and LGPL for libraries - as if the "L" would stand for "Library". But that's wrong! This was never the intention. The "L" stands for "Lesser" and means less protection than GPL, for very special circumstances. According to FSF, you should use LGPL only for libraries that are competing with widely accepted proprietary libraries. For anything new and original, you should use GPL - to promote Free Software. "Why you shouldn't use the Lesser GPL for your next library" https://www.gnu.org/licenses/why-not-lgpl.en.html https://www.gnu.org/licenses/why-not-lgpl.en.html (I disagree with that article in one point: If you compete with pervasive software, use a simple license like ISC/MIT/BSD rather than LGPL, to promote their usage even more.)
  - matt4711 11y ago
    Thanks for clarifying this.
  - UK-AL 11y ago
    It makes the library unusable for anyone, but open source software. If you write any sort of software, and link against this library, boom all the code needs to be GPL'ed. I don't think that's a good thing for promoting a library's use. Most people will just not use the library, and leave a bad taste in there mouth rather than spread the use of GPL. If you want your library to popular don't use GPL. What happens is that someone else comes a long and creates a MIT version. Eventually it gets replaced with the MIT version.
    - vog 11y ago
      > It makes the library unusable for anyone, but open source software. Well, the author is free to dual-license it to propriertary software for some fee - if they want. > I don't think that's a good thing for promoting a library's use But it's a good thing for promoting Open Source! That's the tactic question here: Do you want to promote your name and your library, or do you want to encourage more people to open source their stuff? In general you achieve both, but the question is: Which aspect is more important to you? > If you want your library to popular don't use GPL. What happens is that someone else comes a long and creates a MIT version. See https://news.ycombinator.com/item?id=10158535 https://news.ycombinator.com/item?id=10158535
      - jheriko 11y ago
        i don't buy the rhetoric at face value and i don't think it helps promote open source at all. at best its promoting one flavour of open source methodologies in an authoritarian way. not open source software in general... it does little itself to teach us why open source is good, but its easy to learn why GPL is bad and tar all of open source with the same brush. the MIT and BSD style licenses are open source, but not militant about it. they are doing much better work to promote open source software imo since people will actually use software that is distributed under them in large commercial projects without fear, meaning that open source libraries do actually get used a lot, which lets people learn their advantages first hand... i like your quote about this. that someone will come along and make an MIT version... :)
      - belorn 11y ago
        I have a very different question when I chose license for my software. I ask if my software might end up being used in a product where someone could get sued for sharing software online. I would personally be fine with a new license that simply said "Be nice or don't use my software. You can't sue people who use or share this software. You can't apply for patents and sue people who are being creative and code. You can't stop people from understanding the software that they run on their own machine.". However I doubt many companies would prefer that over GPLv3 so it easier to just use a commonly understood license which Linux distributions understand and find legally acceptable.
  - brlcad 11y ago
    Wow, this is just wrong. The L originally did stand for Library but FSF/Stallman wanted to discourage its use, so it was renamed it to Lesser. LGPL was created to appease authors that didn't want license terms to propagate like GPL, exceptionally common with library and embedded codes. Alas, ignorant authors were also choosing LGPL simply because they were creating a library and FSF didn't like that trend. It was a completely political move to fit their agenda. See https://en.wikipedia.org/wiki/GNU_Lesser_General_Public_License#History https://en.wikipedia.org/wiki/GNU_Lesser_General_Public_Lice...
    - vog 11y ago
      Indeed, the "L" originally stood for "Library", but the FSF declared this to be a mistake as it didn't express their intent. So I think it is fair to say that "L" was never intended to stand for "Library", although it accidentally did for some time.
  - jheriko 11y ago
    > very special circumstances. my experience is that these 'special' circumstances are pretty much "you need to use it in a proprietary production environment" and "you don't want to stop people using your software". this is close to what the FSF say so I don't think i'm far off the mark... the problem with GPL imo is that it is manifestly not free. you must abide by severe restrictions to use the code, which for a lot of software development would incur impractical costs. even if i want people to use my code for free I never use the full GPL license. i don't see any good reason to becasue i never want to dictate what other people can or can't do with their own software by virtue of having helped them out with mine. i really don't understand the sentiment... for example, the choice of GPL here means that nowhere i have ever worked would touch this officially. i can tell you that most of those places are also not thorough enough to stop some random wannabe hotshot programmer from stealing large swathes of code from this repo and using them anyway... (i do not endorse this practice - but i am perhaps a little bitter because i am usually the one who spots these things and has to deal with them).
    - belorn 11y ago
      If you want to define free as "do what you want" then feel free to do so but don't expect everyone to agree with it. I for example live in a free country but I am far from free to do what ever I want. The word "free" has in that single sentence two different definitions, which is why the word liberty is better. But to address one aspect, I do agree that I really don't understand the sentiment to dictate what other people can or can't do with their own software. Suing people for sharing software is wrong, and having EULA's that prevent people from understanding how their software operates is also wrong. The argument that you have to add proprietary licenses in order to earn a living is illogical and only create a world where people don't trust each other.
      - jheriko 11y ago
        i think you have conflated some political rhetoric with reality there. free means free. its an abstract ideal... you do not live in a country where people are free, 'free country' and 'liberty' are politically charged terms which evoke particular ideals, which don't directly map to the meaning of the word 'freedom'. a big part of society is that we willingly give up certain freedoms for the greater good - this is what law is all about. in this particular case i think its clear cut. the GPL stops software from being free compared to an MIT or BSD style license...
- justin66 11y ago
  >The library is very template heavy and thus most of the code is in the header files so I guess it wouldn't change much in this case? Pretty sure the end user is still required to gpl their project if they use your header files. edit: the more I think about this, the sadder I get. You prevented the majority of people from including your software and it doesn't sound like you meant to do it. Might be worth a rethink in the next version.
  - amelius 11y ago
    In spite of its good intentions, a restrictive license such as the GPL is always a weakness and a flaw. I would like to pose the conjecture that any library with a GPL license will eventually be replaced by a library with a more liberal license; the reason is simply because it has one feature extra, which is the more liberal license.
    - vog 11y ago
      > any library with a GPL license will eventually be replaced with a library with a more liberal license That's probably true, but it is not an argument against using the GPL. If your GPL library is original and useful, the cost of reimplementing it will probably higher than the cost of making some depending piece of software Open Source. So during the time until somebody else wrote that ISC/MIT/BSD version (which may be decades, think of GCC versus clang!), lots of other software may have been made Free Software that would otherwise have been proprietary.
      - deleted 11y ago
        [deleted]
      - jeffreyrogers 11y ago
        gcc vs. clang is probably a special case. Code compiled with gcc doesn't become GPL, which is part of why it is so popular.
      - brlcad 11y ago
        I love open source and appreciate free software tenants, but think this is absolutely an argument against using the GPL for library-style codes. Your point is an ancillary benefit. Most authors don't publish libraries to encourage the greater FSF-ecosystem or free software agenda -- they publish to make it available to others and see it get put to use. Picking a license that limits prevalence of use is contrary to that objective, plain and simple. It also does not necessarily follow that proprietary would have been the alternative to free software. Published as ISC/MIT/BSD, lots of additional open source software would have been able to make use of the library, advanced more quickly, more easily permitted additional open source and free software derivatives, etc. More power to authors that choose to use GPL on a library code, as they are certainly entitled to do so, but it is a substantially limiting factor in the near and long term. We do not have to agree on these points. ;)
- brlcad 11y ago
  It would absolutely change. GPL defines any incorporation or usage of a GPL work as a derivative work, thus effectively only permitting other GPL codes to use this library. That means any software in the Apache, Eclipse, or BSD-style ecosystems (among many others) cannot use this. As for multiple authors, in theory you were required to have their permission to release it under the GPL (or any other open source license) in the first place. Given your uncertainty, it's possible that permission wasn't obtained and you could already be on unstable legal ground. I would reach out to all contributors and ask them for permission to release under a more flexible license like BSD/MIT or Apache2 to encourage more widespread use.
ioquatix 11y ago
Why not the MIT or BSD license? It would be more useful for other developers.
- KqAmJQ7 11y ago
  Quiet, Richard Stallman might hear you!
- vog 11y ago
  I beg to differ. I'm always happy to use external GPL libraries as an excuse for making stuff Open Source. Whenever I talked to unsure customers or managers, this was the single most convincing argument. Of course, this only works if people aren't strictly against creating Free Software, but in that case you have lost anyway.
  - qznc 11y ago
    So you actively use the viral aspect of the GPL to make more stuff Open Source. Probably what Stallman intended. :)
    - vog 11y ago
      > Probably what Stallman intended. Probably? Is is exactly what he intended and what he asks the community to do. :-)

lorenzhs 11y ago

The SDSL is very easy to use, and its versatility is quite amazing. It's also rather interesting to look at the list of papers that cite it: https://scholar.google.com/scholar?cites=6772708594529960585 https://scholar.google.com/scholar?cites=6772708594529960585 and https://scholar.google.com/scholar?q=SDSL-lite https://scholar.google.com/scholar?q=SDSL-lite

amelius 11y ago

How does it compare in terms of memory and speed, to the GNU implementation of STL?

jbandela1 11y ago

Cool library. Any thoughts on getting it to work with Visual C++ 2015. It now has pretty decent C++11 support, you already use CMake, and this library seems like something that is inherently OS neutral. Even when I am ultimately deploying on Linux, I will often develop and debug my os-independent logic using Visual C++ on Windows and then when that is working well, recompile using g++ or clang++.

matt4711 11y ago
We are working on VS support. Last time we tried to port to VS some of the constexpr stuff we use was not available yet. The next release (in 1-2 month) should have full VS2015 support.
- kjs3 11y ago
  Um...is that legal? Nothing in VS is licensed GPLv3.

jheriko 11y ago

this looks very cool but it is a shame about the license and a shame about the code style. STL is a poor exemplar to follow - its a real wasteland of a library and very deficient compared to libraries for other modern languages. however i will now go and learn these things and reinvent some wheels to make myself a better programmer. thanks. :)