6 ms·

SDSL – Succinct Data Structure Library for C++

79 points by vsbuffalo 11y ago

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
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... :)
  - 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.
  - 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. :-)
  - KqAmJQ7 11y ago
    Quiet, Richard Stallman might hear you!
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

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

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... :)
- 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.
- 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. :-)
- KqAmJQ7 11y ago
  Quiet, Richard Stallman might hear you!

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. :)