[RESOLVED] miniLZO compression/decompression library

[Arnoutdv]

Has anyone already created binaries from the miniLZO source to be used from VB?
I don't have access to a C-Compiler and I'm not that good in creating the interface to be used within in VB6.

Source:
http://www.oberhumer.com/opensource/lzo/

[dz32]

[...]

[Arnoutdv]

Great, I will have a look at it!

Very curious how it it performs compared to Zlib.
If the compression rate for my data is close to this of ZLib and decompression speed is indeed twice as good then it's very promising.

[Schmidt]

Very curious how it it performs compared to Zlib.
If the compression rate for my data is close to this of ZLib and decompression speed is indeed twice as good then it's very promising.

Here's a comparison for that (using the 3 RC5-built-in compression-schemes):
The compressor which is comparable to LZO is FastLZ (slightly slower in compression,
but also slightly faster in decompression): http://fastlz.org/

I've tested with Bible12.txt (about 5MB, downloadable here: https://www.gutenberg.org/files/30/old/
which should be placed in the App.Path of the VB-Project, which contains the following Form-Code
(also in the App.Path should be the minilzo.dll for the example to work)

Option Explicit 'needs a reference to vbRichClient5

Private Declare Function FreeLibrary Lib "kernel32" (ByVal hLibModule As Long) As Long
Private Declare Function LoadLibrary Lib "kernel32" Alias "LoadLibraryA" (ByVal lpLibFileName As String) As Long

Enum eMsg
  em_version = 0
  em_lastErr = 1
End Enum
    
Private Declare Function Compress Lib "minilzo.dll" (ByVal bufIn As Long, ByVal inSz As Long, ByVal bufOut As Long, ByVal outSz As Long) As Long
Private Declare Function DeCompress Lib "minilzo.dll" (ByVal bufIn As Long, ByVal inSz As Long, ByVal bufOut As Long, ByVal outSz As Long) As Long
Private Declare Function LZOGetMsg Lib "minilzo.dll" (ByVal Buf As String, ByVal sz As Long, Optional ByVal msgid As eMsg = em_version) As Long

Private hLib As Long

Private Sub Form_Load()
  hLib = LoadLibrary(App.Path & "\minilzo.dll")
End Sub

Private Sub Form_Click()
  FontName = "Arial": FontSize = 10
  AutoRedraw = True: Cls
  
  Dim Crypt As cCrypt
  Set Crypt = New_c.Crypt 'instantiate the RC5-Crypt- and Compression-helper

  Dim B() As Byte, BCmp() As Byte, BDec() As Byte, i As Long, sC As String
      B = New_c.FSO.ReadByteContent(App.Path & "\bible12.txt")
  
  For i = 0 To 3
    New_c.Timing True
      Select Case i
        Case 0: sC = "LZO":    LZO B, BCmp
        Case 1: sC = "FastLZ": Crypt.FastLZCompress B, BCmp
        Case 2: sC = "ZLib":   Crypt.ZlibCompress B, BCmp
        Case 3: sC = "LZMA":   Crypt.LZMAComp B, BCmp, 6
      End Select
    Print sC; " ", Format(UBound(BCmp) / UBound(B), "Percent"); " "; New_c.Timing,
    
    New_c.Timing True
      Select Case i
        Case 0: LZO BCmp, BDec, UBound(B) + 1
        Case 1: Crypt.FastLZDecompress BCmp, BDec
        Case 2: Crypt.ZLibDecompress BCmp, BDec
        Case 3: Crypt.LZMADeComp BCmp, BDec
      End Select
    Print "DeComp-success: "; StrComp(B, BDec) = 0, New_c.Timing
    
    Erase BCmp
    Erase BDec
  Next i
End Sub
 
'for decompression, it would probably be better to pass in the original size to get an idea
'of the buffer size to allocate. in practice I would include a header in comporessed data
'that included original size and original md5
'
'note: passing in orgCompressedSize tells it you want to decompress the data..
Function LZO(Buf() As Byte, bOut() As Byte, Optional orgCompressedSize As Long = 0) As Boolean
Dim inSz As Long, sz As Long, outlen As Long

    inSz = UBound(Buf) + 1
    If orgCompressedSize = 0 Then
        outlen = inSz * 2
    Else
        outlen = orgCompressedSize * 2
    End If
    
    ReDim bOut(0 To outlen - 1)
    
    If orgCompressedSize = 0 Then
        sz = Compress(VarPtr(Buf(0)), inSz, VarPtr(bOut(0)), outlen)
    Else
        sz = DeCompress(VarPtr(Buf(0)), inSz, VarPtr(bOut(0)), outlen)
    End If
    
    If sz < 1 Then
       MsgBox "Compression failed: " & LZOMsg()
    Else
      ReDim Preserve bOut(0 To sz - 1)
      LZO = True
    End If
End Function

Function LZOMsg(Optional m As eMsg = em_lastErr)
    Dim ver As String
    Dim sz As Long
    
    ver = String(500, Chr(0))
    sz = LZOGetMsg(ver, Len(ver), m)
    If sz > 0 Then
        ver = Mid(ver, 1, sz)
        LZOMsg = ver
    End If
End Function

Output then (for those who don't want to run it themselves):


HTH

Olaf

[Arnoutdv]

Ouch these results are quite disappointing, especially when the target file was just a text file
Quite a big difference in compression rate and just slightly better in decompression speed.

I'm going to do some test on the typical dataset I use.
Arrays of longs which are actually bitvector arrays.
I need to decompress around 2000 of these arrays per calculation day.
Size does matter because my files, which is an archive with about 3000 compressed bitvector arrays, are about 5-7MB per day.
If the files are twice as big then reading the files into memory takes also twice as much time.
These files are typically read from a network share.

So I'm going to do some tests with LZO, but also with FastLZ from vbRichClient.

[Schmidt]

Quite a big difference in compression rate and just slightly better in decompression speed.

I'm going to do some test on the typical dataset I use.

The results will get closer to what you've probably expected, with increased entropy of the
input-stream (when the data is less redundant, and/or does follow less predictable patterns) -
e.g. when compressing compiled binaries...

Below is the results when compressing/decompressing the (about 2.5MB) vb_cairo_sqlite.dll:


So the differences in compression-ratio are now less between ZLib and the fast compressors -
whilst the decoding-speed got better (relatively, compared to ZLib) - now more than twice
as fast.

From what you wrote about the nature of your Data (BitVectors), I guess you might see
similar tendencies.

Olaf

[dz32]

[...]

[Schmidt]

one other thought on the lzo, in my example I was a little lazy I always allocated 2x teh buffer size needed, on big files this could be noticable, you can optimize here and see what typically works, maybe outlen = sz+(sz/3) . Then again may not be noticeable at all. have to play with it and see.

I dont know where ucl falls on the scale but I also have a dll for that laying around

https://github.com/dzzie/libs/tree/m...UCLCompression

I guess it will sit between LZO and ZLib - but googling about the topic some more,
there seems to be a "new star" among the fast compressors:
LZ4 -> http://cyan4973.github.io/lz4/

Also note, that the codecs from Oberhumer (which are all under GPL) -
do not allow commercial distribution along with closed-source-binaries (your App).

Whilst FastLZ (MIT) - and LZ4 (BSD) will allow commercial usage/distrubution.

Olaf

[Arnoutdv]

The license for LZO could also be a showstopper.
Thanks for the link to LZ4, have to do some reading on this.
Whether it supports direct memory compression like LZO, Zlib and the compression libraries used in vbRichClient.

@Olaf, your interface to the compression routines used in vbRichClient do store additional information in the compressed byte array, don't they?
And the decompression routines also expect some additional information in the byte array?
Because I currently use zlibwapi.dll and use the "raw" compressed data and I do have my own descriptors in the data to set the decompression buffer size.

[Arnoutdv]

Did some tests on my own dataset.

The data consists of 4.217 files (actually arrays), the original size is: 437.5MB
Currently using ZLib compression the compressed archive has a size of 5.9MB
Using LZO the data is compressed to 11.2MB.
The decreased decompression time doesn't make up for additional time needed to read the file.

I also tested QuickLZ and BZip2.
QuickLZ has an even worse compression ratio then LZO.
BZip2 does a better job on the data compression compared to ZLib (5.3MB) but is very slow when decompressing.

So it seems the overall winner for my situation is still ZLib.

I will do an additional test using FastLZ, but the current issue is the additional bytes added by the vbRichClient interface.

Thanks all for your input

[jj2007]

If it's for your own use, FreeArc is clearly the best.

[Arnoutdv]

Thanks, but It's not for private use and I need a in-memory (de)compression.

[wqweto]

If you need zlib compression ratios w/ 3-4x performance increase take a look at the (still unstable) zstd project: https://github.com/Cyan4973/zstd

Edit: Here is a nice compression libraries benchmarks site: https://quixdb.github.io/squash-benchmark/

There I found a small C/C++ library pithy I've never heard before. My VB6 porting effort is WiP but still you can test the stdcall build of the library from `bin/debug_pithy.dll`.

From sample project in `test` directory I get not bad compression ratio for max compression level of 9 and blazing decompression speed on a single core

Compression ratio: 17.71% (3'276'800 -> 580'362)
Compression speed: 312.50MB in 903 ms -> 346.07 MB/s
Decompression speed: 312.50MB in 546 ms -> 572.34 MB/s

The input file is a MSSQL database that gets zipped to 443'249 bytes. The compression/decompression speed is for 100 iteration over input file. My CPU is i7-4770 @ 3.50GHz overclocked to 3.9GHz

Here are the results for bible12.txt

Compression ratio: 39.37% (5'213'926 -> 2'052'718)
Compression speed: 497.24MB in 3196 ms -> 155.58 MB/s
Decompression speed: 497.24MB in 1404 ms -> 354.16 MB/s

And the zip from the link is 1'459'169 bytes

Here are the results for vb_cairo_sqlite.dll

Compression ratio: 60.28% (2'596'352 -> 1'565'013)
Compression speed: 247.61MB in 1784 ms -> 138.79 MB/s
Decompression speed: 247.61MB in 678 ms -> 365.20 MB/s

And the zip is 1'226'299 bytes

The VC2015 optimized build gets another 30% performance increase to 465.58 MB/s decompression speed on bible12.txt but have other issues.

cheers,
</wqw>

[Schmidt]

Since the new SQLite-version 3.12 was just released, I've used the
occasion to include LZ4 into the __stdcall-compile of vb_cairo_sqlite.dll now.
(Uploaded and available in the new RC5-BaseLib-package -> 5.0.43)...

LZ4 is performing very nicely (especially with regards to decompression-speed,
which is > 1GB/sec) - and so I've also decided to switch over to it in favour
of FastLZ (LZ4 now working behind the scenes of the highlevel-Methods for
cCrypt.FastLZCompress/Decompress - though FastLZDecompress is still capable
to decompress Blobs which were formerly encoded with the FastLZ-algo).

Here's the results for Bible12.txt again:


And here those for vb_cairo_sqlite.dll:


@wqweto
would be nice if you could test its performance on your fast machine - as said, it
sits behind cCrypt.FastLZ... now (in case you want to use the high-level-API) -
the exposed Flat-APIs are below (if you want to use it more low-level):

The above results were (compression-wise) achieved with LZ4_compress_HC @ CmpLevel 2
(LZ4_HC does additional Block-Analysis to achieve the higher compression at the cost of some
encoding-speed).

Declare Function LZ4_compress_default Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long) As Long
Declare Function LZ4_compress_HC Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long, Optional ByVal CmpLevel As Long = 2) As Long
Declare Function LZ4_decompress_safe Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long) As Long

The ReturnValues indicate success, when the Results are > 0 - and the "Max-OutBufferSize-Estimate"
in case of the compression can be safely pre-calculated with (InBufSize * 256/255 + 16).

Olaf

[jj2007]

You wrote that you need in-memory compression and decompression. Does that mean you can't use an external exe to compress?
I am curious, since I also would like to find a DLL or lib that I could link to my own programs.

For comparison, FreeArc results on a Core i5:

FreeArc 0.666 creating archive: bib.arc
Compressed 1 file, 5,213,926 => 876,024 bytes. Ratio 16.8%
Compression time: cpu 0.81 secs, real 0.86 secs. Speed 6,077 kB/s

[Schmidt]

You wrote that you need in-memory compression and decompression. Does that mean you can't use an external exe to compress?

I'd think a lib is more comfortable to use for that (no stdIn/stdOut-piping needed, and no "ShellAndWait").

For comparison, FreeArc results on a Core i5:

FreeArc 0.666 creating archive: bib.arc
Compressed 1 file, 5,213,926 => 876,024 bytes. Ratio 16.8%
Compression time: cpu 0.81 secs, real 0.86 secs. Speed 6,077 kB/s

FreeArc is not bad (with a good "over-all-profile") - but still not among the "fast compressors"
which we basically talk about here...

These can be used, to e.g. accomplish a well-performing "In-App-Caching" (which I think
ArnoutDV is after) - so, in a caching-scenario one usually compresses a given ByteArray-Blob once
(compression-speed not all *that* important whilst storing a new Blob) - but then, when multiple repeated
reads are to be performed against the compressed and cached Blob (e.g. sitting in a Hash-Table or Collection),
a superfast Decompression (with nearly no difference to uncompressed Memory-transfers) would be a nice thing to have.

When the compression-ratio is about, say 1/3 - one can cache 3 times as many Blob-Items InMemory,
compared to uncompressed storage - with a still decent "Cache-Read-Performance".

Another scenario which makes the Compression-to-speed-ratio more obvious (and where these
fast compressors make sense) is e.g. "Online-Transfer-Times" from e.g. a Web- or AppServer.

When we e.g. assume, that the "typical Inet-Transfer/Download-speed" is currently at 32MBit/sec on average
(over different Inet-Clients which all have access to the Web- or AppServer) - then let's simplify and say,
that the server will transfer e.g. ResultSets from DB-Selects at roughly 4MByte/sec back to the Clients.

Now let's do some math (assuming a concrete Resultset with an uncompressed size of 1MB) -
and with our assumed average Inet-Transfer-speed of ~4MByte/sec the 1MB would need:
- 0.25sec to reach (and be directly available) to a given Client when transferred uncompressed

Now with an assumed ~100MByte/sec compress-speed and ~1GByte/sec decompress-speed in case of LZ4,
we could do compressed transfers of that 1MB-Recordset - and assuming we reach ~40% size-reduction,
the calculation would be:
- time for serverside compression with 100MByte/sec: 0.01sec
- transfertime for the (to 400KB) reduced Resultset: 0.1sec
- time for clientside decompression with 1GByte/sec: 0.001
Total time until the Rs is available at the clientside: 0.111sec

Now the same transfer again, with FreeArc-compression (assuming a reduction to 20%,
with a compression-speed of 6MB/sec - and a decompression-speed of 50MB/sec).
- time for serverside compression with 6MByte/sec: 0.16sec
- transfertime for the (to 200KB) reduced Resultset: 0.05sec
- time for clientside decompression with 50MByte/sec: 0.02
Total time until the Rs is available at the clientside: 0.23sec

So that result is (although timing-wise better than the "raw-transfer") still about
two times slower, compared to the transfer which was accomplished with the faster compressor
(and it would cause a much higher server-load CPU-wise).

So these fast compressors have their use-cases, despite their lower compression-rates.

Olaf

[wqweto]

@Olaf: Here are LZ4 results on my CPU

LZ4 Compression Level 1 ratio: 39.92% (5'213'926 -> 2'081'294)
LZ4 Compression speed: 497.24MB in 6548 ms -> 75.94 MB/s
LZ4 Decompression speed: 497.24MB in 851 ms -> 584.30 MB/s
LZ4 Compression Level 2 ratio: 37.30% (5'213'926 -> 1'944'787)
LZ4 Compression speed: 497.24MB in 6541 ms -> 76.02 MB/s
LZ4 Decompression speed: 497.24MB in 851 ms -> 584.30 MB/s
Pithy Compression ratio: 39.37% (5*213*926 -> 2'052'718)
Pithy Compression speed: 497.24MB in 2773 ms -> 179.31 MB/s
Pithy Decompression speed: 497.24MB in 1103 ms -> 450.81 MB/s

Compared to pithy LZ4 shows clearly faster decompression but traded 2x slower compressor for some (marginal) 2% compression gains.

Did you compile the dll with /O2 /Ox optimizations? Is this VC6 compiled or newer? I noticed considerable perf gains w/ VC2015 release builds.

@jj2007: For me it's not "clear" that FreeArc is the best. I'm very happy with nanozip performance for my particular payload -- MSSQL database backups.

Most people would consider anything slower than zip performance an overkill on CPU resources. There are lots of very tight but quite slow compression schemes (BWT comes to mind) that are not pratical for GB payloads e.g. I need to compress 300GB backups daily.

Here are some results FreeArc vs nanozip vs plain zip on my CPU

D:\TEMP>Arc.exe a bible12 bible12.txt
FreeArc 0.666 creating archive: bible12.arc
Compressed 1 file, 5,213,926 => 876,024 bytes. Ratio 16.8%
Compression time: cpu 0.53 secs, real 0.64 secs. Speed 8,184 kB/s
All OK

D:\TEMP>nz a bible12 bible12.txt
NanoZip 0.09 alpha/Win64  (C) 2008-2011 Sami Runsas  www.nanozip.net
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz|24278 MHz|#4+HT|2797/8135 MB
Archive: bible12.nz
Threads: 4, memory: 512 MB, IO-buffers: 4+1 MB
Compressor #0: nz_optimum1 [44 MB]
Compressed 5 213 926 into 802 536 in 0.41s, 12 MB/s
IO-in: 0.00s, 4972 MB/s.

D:\TEMP>nz a -cd -p1 bible12-cd bible12.txt
NanoZip 0.09 alpha/Win64  (C) 2008-2011 Sami Runsas  www.nanozip.net
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz|27212 MHz|#4+HT|2790/8135 MB
Archive: bible12-cd.nz
Threads: 4, memory: 512 MB, IO-buffers: 20+4 MB
Compressor #0: nz_lzhd [13 MB]
Compressed 5 213 926 into 1 324 633 in 0.11s, 45 MB/s
IO-in: 0.00s, 4972 MB/s.

D:\TEMP>d:\utils\ptime "D:\Program Files\7-Zip\7z.exe" a -tzip bible12 bible12.txt | findstr /i time
ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Execution time: 0.850 s

. . . and bible12.zip got down to 1'369'886 bytes -- very close to nz_lzhd result.

I'm running nz_lzhd compressor on 2 cores for any file above 1GB with `nz a -cd -p2 -m2g` for 3-4 times the performance of plain zip (which is single core by nature) and get always (somewhat) better compression at the end. I fiddled several times but couldn't find FreeArc compressor w/ equivalent perf vs compression ratio. Probably it's CPU dependant too.

cheers,
</wqw>

[jj2007]

> For me it's not "clear" that FreeArc is the best. I'm very happy with nanozip

Differences are not big. http://compressionratings.com/rating_sum.html and http://www.maximumcompression.com/da...ry_mf.php#data see FreeArc and NanoZip very close. NZ seems to be in a permanent limbo, though.

@Olaf: Thanks for the examples. Indeed, FA+NZ serve a different purpose.

[Arnoutdv]

The results on typically single day dataset, I didn't test the decompression speed yet, only the size of the created archive.
All arrays in the archive consists of 840038 elements, being either Bits, Bytes, Integers, Longs, Singles or Doubles
The bits are actually stored in Longs (32 bits in a Long)

Currently the dataset is compressed using ZLib (zlibwapi 1.2.5) using compression level 9.
Which is the second column in both rows [Zlib (CL=9)]

Library        Uncompressed  Zlib (CL=9)    LZO 2,09      FastLZ      LZMA 9      LZMA 4     QuickLZ       BZip2
4217 arrays     458,779,436    6,232,353  11,746,874  11,032,075   5,421,074   5,969,993  14,536,131   5,465,663
                    437.5MB        5.9MB      11.2MB      10.5MB       5.2MB       5.7MB      13.9MB       5.2MB
                 Index ZLib         0.0%      +88.5%      +77.0%      -13.0%       -4.2%     +133.2%      -12.3%

Library        Uncompressed  Zlib (CL=9)   vbRC zLib         LZ4     LZ4 HC9    LZ4 HC16     LZ4 HC4     LZ4 HC2  
4217 arrays     458,779,436    6,232,353   6,565,218   9,739,272   8,762,553   8,607,041   9,191,936   9,705,545  
                    437.5MB        5.9MB       6.3MB       9.3MB       8.4MB       8.2MB       8.8MB       9.3MB  
                 Index ZLib         0.0%       +5.3%      +56.3%      +40.6%      +38.1%      +47.5%      +55.7%

Decompressing all arrays just once takes an average of 468ms on my computer.
Up until now it seems ZLib seems preferable, compression is very good, decompression speed is also okay.
For LZMA, LZ4 and FastLZ I used the vbRichClient interface.

[wqweto]

Had some time to compile a VB6 compatible dll from ZSTD library mentioned above. Here are its results compared to Zlib from vbRC5

Zlib Compression Level ratio: 28.00% (5'213'926 -> 1'459'907)
Zlib Compression speed: 497.24MB in 28998 ms -> 17.15 MB/s
Zlib Decompression speed: 497.24MB in 2089 ms -> 238.03 MB/s

ZSTD Compression Level 1 ratio: 30.96% (5'213'926 -> 1'614'265)
ZSTD Compression speed: 497.24MB in 3989 ms -> 124.65 MB/s
ZSTD Decompression speed: 497.24MB in 1950 ms -> 254.99 MB/s

ZSTD Compression Level 5 ratio: 27.74% (5'213'926 -> 1'446'149)
ZSTD Compression speed: 497.24MB in 8590 ms -> 57.89 MB/s
ZSTD Decompression speed: 497.24MB in 2254 ms -> 220.60 MB/s

ZSTD Compression Level 7 ratio: 25.79% (5'213'926 -> 1'344'691)
ZSTD Compression speed: 497.24MB in 14535 ms -> 34.21 MB/s
ZSTD Decompression speed: 497.24MB in 1899 ms -> 261.84 MB/s

ZSTD Compression Level 10 ratio: 24.70% (5'213'926 -> 1'288'097)
ZSTD Compression speed: 497.24MB in 30686 ms -> 16.20 MB/s
ZSTD Decompression speed: 497.24MB in 1783 ms -> 278.88 MB/s

ZSTD Compression Level 14 ratio: 24.13% (5'213'926 -> 1'258'209)
ZSTD Compression speed: 497.24MB in 82613 ms -> 6.02 MB/s
ZSTD Decompression speed: 497.24MB in 1776 ms -> 279.98 MB/s

Better by a slight margin IMO. Probably the compressor is worth it, decompression speed is on par with zlib. Compression level 7 looks most promising replacement for zlib. This lib can use a data dictionary trained on your data but the API is more complicated. It supports streaming mode, useful if you are compressing and sending data down a socket to the client simultaneously.

Here is the basic helper VB6 module I'm using in the tests

Option Explicit

Private Declare Function LoadLibrary Lib "kernel32" Alias "LoadLibraryA" (ByVal lpLibFileName As String) As Long
Private Declare Function ZSTD_compress Lib "debug_zstd" (dst As Any, ByVal maxDstSize As Long, src As Any, ByVal srcSize As Long, ByVal CompressionLevel As Long) As Long
Private Declare Function ZSTD_decompress Lib "debug_zstd" (dst As Any, ByVal maxDstSize As Long, src As Any, ByVal srcSize As Long) As Long
Public Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)

Public Sub ZstdInit()
    Call LoadLibrary(App.Path & "\debug_zstd.dll")
End Sub

Public Function ZstdCompress(baSrc() As Byte, baDst() As Byte, Optional ByVal CompressionLevel As Long = 5) As Boolean
    Dim lTemp           As Long
    Dim lSize           As Long
    
    lSize = 2 * (UBound(baSrc) + 1) + 4
    ReDim baDst(0 To lSize) As Byte
    lSize = ZSTD_compress(baDst(4), UBound(baDst) - 3, baSrc(0), UBound(baSrc) + 1, CompressionLevel)
    If lSize > 0 Then
        lTemp = UBound(baSrc) + 1
        Call CopyMemory(baDst(0), lTemp, 4)
        ReDim Preserve baDst(0 To lSize + 3)
        ZstdCompress = True
    End If
End Function

Public Function ZstdDecompress(baSrc() As Byte, baDst() As Byte) As Boolean
    Dim lSize           As Long
    
    Call CopyMemory(lSize, baSrc(0), 4)
    If lSize > 0 Then
        ReDim baDst(0 To lSize - 1) As Byte
        lSize = ZSTD_decompress(baDst(0), lSize, baSrc(4), UBound(baSrc) - 3)
        ZstdDecompress = lSize > 0
    End If
End Function

cheers,
</wqw>

[Schmidt]

The results on typically single day dataset,

Quite an impressive accumulation of results - thanks for the list...

All arrays in the archive consists of 840038 elements, being either Bits, Bytes, Integers, Longs, Singles or Doubles
The bits are actually stored in Longs (32 bits in a Long)

When you say, that your daily raw-data consists of 840038 elements,
do you mean an UDT (or an Array of said UDT) - does it have "SubArrays" in the TypeDef?

The reason I ask is, that you might save quite some space, when the
serialization of the Members of that structure always results in the same
BytePosition for a given Entry within the serialization-stream...

In that case you could try to save e.g. "a whole week" in roughly the same
space - in case there's only slight differences "from day to day".

What I mean is, that you could calculate "the differential" between two
days per XOR - and then compress only the "XORed Result-stream".

Demonstrated with two Longs here, which only change by a simple increment:

Say, the first Long (on Monday) is: 12345678 ... and on the next day ...
(Tuesday) it's just incremented by 1: 12345679

What you currently do is, to compress 12345678 on Monday -
and 12345679 on Tuesday.

What you could consider is, that when you create "weekly archives",
you would only "fully compress" Monday (with the old scheme, similar to
a "Key-Frame" in a Video-stream) - and all the rest of the weekdays
with "XOR-Differentials".

In case of our Example... 12345678 XOR 12345679 = 1 ...
the compressor would see a "nearly empty byte" (the result 1) -
followed by three emtpy Bytes at the given Long-Position in the stream.
.

To restore the Tuesday-Value from Monday and the Differential,
you would only need to apply the XOR again: 12345678 XOR 1 = 12345679

Not sure, whether that is applicable in your scenario - just wanted to
mention the approach...

Olaf

[jj2007]

In that case you could try to save e.g. "a whole week" in roughly the same
space - in case there's only slight differences "from day to day".

Nice idea, Olaf! I wonder to what extent compressors wouldn't do that automatically. Most of them use a big window to find duplicates, so having seven times a similar dataset should lead to very good ratios. A quick test with FreeArc and 7-Zip:

21.03.97  16:31         4,047,392 bible.txt
25.03.15  00:19       404,739,200 Bible100.txt

31.03.16  05:08         1,113,712 bible.zip
31.03.16  05:10       111,143,060 Bible100.zip
31.03.16  05:08           734,215 bible.arc
31.03.16  05:08        35,658,471 Bible100.arc

Both could do much better IMHO, maybe there are settings to enlarge the window size. FA took a few seconds, 7z took ages to complete.

[Arnoutdv]

Had some time to compile a VB6 compatible dll from ZSTD library mentioned above

Great, thanks! I'm going do so some tests with it.
I will get back to you

[Arnoutdv]

When you say, that your daily raw-data consists of 840038 elements,
do you mean an UDT (or an Array of said UDT) - does it have "SubArrays" in the TypeDef?

I understand what you mean with this type of Delta Packing.
But every day is too different compared to the previous day.

The data consists of panel research statements (behavior).
All data is just in a big binary blob.
There are normal data arrays like an array for the panelistIDs and duration of the statement.
Then there are bitvector arrays with a key like "activityid=3", "activityid=8", "location=1", "location=4", "brandid=123", "brandid=4" etc etc

When reading a daily file everything is stored in memory as a big blob, a byte array.
The file also contains a dictionary describing every array in the data:
-key
-offset
-length
-uncompressed_length
-compression_method
-data_type (vbByte, vbInteger ...)

These dictionary items are stored in an UDT array, the key/index pair in a cSortedDictionary.
Then based on the key the index in the UDT is quickly found

These bitvectors are used for pseudo queries like: "(activityid=3&location=1)|(activityid=4&brandid=4)"
The bitvectors combined with "AND" and "OR" relations, returning a new bitvector array.
Then a new function is called to return the set indices from the returned bitvector.
Theses indices are then used to count the panelists and their duration from the base arrays.

[Arnoutdv]

A lot my arrays have only sparse values in them, ZLib does stunning compression on this data.

Example:
An array of 840,038 bits, needs 105,008 longs to store the results, but only a few bits are set.
Zlib compresses this array of longs to 130 bytes
ZLib: 130 bytes
LZMA: 94 bytes
LZO: 498 bytes
FastLZ: 439 bytes
LZ4 : 429 bytes

I also have a method which on my data works well for having additional compression.
It's just simply reordering the data in chunks, based on a parameter:
Chunk = 2 -> 1,3,5,7,9... followed by 2,4,6,8,10...
Chunk = 4 -> 1,5,9,13..., 2,6,10,14..., 3,7,11,15..., 4,8,12,16...

This leads often to much better compression, but the downsize is the data has to be re-ordered again after each decompression call.
So at the end I don't use this method for live applications.

Also sometimes using DeltaCompression on the array itself does help, but again this has quite some impact on the performance.

Private Sub ReOrderData(bBytes() As Byte, bReorderOffset As Byte)
  Dim lNofBytes As Long
  Dim bReorder() As Byte
  Dim lCnt As Long, lIndex As Long, l As Long
  Dim lReorderOffset As Long
  
  If bReorderOffset < 2 Then Exit Sub
  
  lReorderOffset = bReorderOffset
  lNofBytes = UBound(bBytes) + 1
  ReDim bReorder(lNofBytes - 1)
  
  lCnt = 0
  For lIndex = 0 To lReorderOffset - 1
    For l = lIndex To lNofBytes - 1 Step lReorderOffset
      bReorder(lCnt) = bBytes(l)
      lCnt = lCnt + 1
    Next l
  Next lIndex
  CopyMemory bBytes(0), bReorder(0), lNofBytes
  Erase bReorder
  
End Sub

Public OrderData(bBytes() As Byte, bReorderOffset As Byte)
  Dim lNofBytes As Long
  Dim bReorder() As Byte
  Dim lCnt As Long, lIndex As Long, l As Long
  Dim lStepSize As Long, lReorderOffset As Long
  
  If bReorderOffset < 2 Then Exit Sub
  
  lReorderOffset = bReorderOffset
  lNofBytes = UBound(bBytes) + 1
  ReDim bReorder(lNofBytes - 1)
  
  lStepSize = CLng((lNofBytes) / lReorderOffset + 0.5)
  For l = 0 To bReorderOffset - 1
    For lIndex = 0 To lStepSize - 1
      If (l + lIndex * lReorderOffset) < lNofBytes Then
        bReorder(l + lIndex * lReorderOffset) = bBytes(lCnt)
        lCnt = lCnt + 1
      End If
    Next lIndex
  Next l
  CopyMemory bBytes(0), bReorder(0), lNofBytes
  Erase bReorder

End Sub

Private Sub DeltaEncode(bBytes() As Byte)
  Dim i As Long
  Dim btDelta As Byte, btOriginal As Byte
  Dim iBuffer As Integer
  
  btDelta = 0
  For i = 0 To UBound(bBytes)
    btOriginal = bBytes(i)
    iBuffer = CInt(btOriginal) - btDelta
    If iBuffer < 0 Then iBuffer = iBuffer + 256
    bBytes(i) = iBuffer
    btDelta = btOriginal
  Next i
  
End Sub

Private Sub DeltaDecode(bBytes() As Byte)
  Dim i As Long
  Dim btDelta As Byte
  Dim iBuffer As Integer
  
  btDelta = 0
  For i = 0 To UBound(bBytes)
    iBuffer = CInt(bBytes(i)) + btDelta
    If iBuffer > 255 Then iBuffer = iBuffer - 256
    bBytes(i) = iBuffer
    btDelta = iBuffer
  Next i
  
End Sub

[Schmidt]

A lot my arrays have only sparse values in them, ZLib does stunning compression on this data.

There's "Sparse-Matrix"-approaches, to hold such data efficiently InMemory
(no need for "blown-up, normal Arrays" in such cases).

I also have a method which on my data works well for having additional compression.
It's just simply reordering the data in chunks, based on a parameter:

And that hints at, that (along to the way you stored your Data) - you might
have destroyed 'context' (Values which better be kept tightly together in a
sequence were moved "out of location").

On a more general note...

I don't have experience with "panel-research" - but I could imagine that
the "true raw data" which daily comes in from a kind of "survey-program",
might be much less "voluminous" than your current ~450MB.

With "true raw data" I mean that this data should not contain anything which
was derived by some math - or AND/OR-combined extra-queries - not sure
how much (or if at all) of such "artificially generated" data is currently contained
in your (uncompressed) daily 450MB.

Isn't there a simple (2D-DataTable-like) scheme behind such surveys -
with simple "Field-Header-Columns" like:

RespondentID, ActivityID, LocationID, BrandID, SatisfactionID, etc.

I mean, there's only so much "raw-data" a willing respondent (who's part of a panel),
is willing to provide in a daily fashion (the above table perhaps not having more
than 20 Columns or so).

Then the amount of daily raw-data (the Rows in above table) is only dependent
on the count of the respondents...

Simply cannot imagine, that this Raw-Table amounts to a daily volume of
450MB (uncompressed).

So my suspicion is, that you're trying to precalculate kind of like an
"OLAP-cube", based on a "Star-Schema" or something - to be able to
deliver "fast answers in any context" - and that these pre-calculations
are responsible for the 450MB?

Olaf

[Arnoutdv]

Hi Olaf,

No it's not pre-generated data.
They are behavior statements.
Like watching TV or, some other dataset, internet behavior

The huge uncompressed dataset comes from all the "index" tables.
For example I could have a single array holding the current ActivityID.
But then I would have to loop through the data when reporting ActivityIDs, to see whether the current ActivityID matches one of the ActivityIDs I want to report.
That's why I have for all ActivityIDs used in the current dataset a BitVector to indicate in which row an Activity is used.
If there are 99 unique ActivitityIDs there would be 99 ActivityID bitvectors arrays.
When dealing with Internet research there can be easily 5000+ ActivityIDs (aka websites).
The number of Respondents vary, around 3000-5000 for TV research and between 50K-90K for internet research.

Instead of BitVectors you can also use index arrays, in which only the used "row numbers" are stored.
This give indeed much less uncompressed data, but doing "AND" "OR" relations on multiple arrays is much slower than doing bit operations on long arrays, which also does the bit operation on 32 rows in a single statement.
I tried it using MergeList routines for (sorted) long arrays.
But the constantly redimming of the output array costs time
I have a MergeList for Union and for Intersection. They are fast, but not as fast as doing bit operations.

But in both cases I would compress the data.

Private Function MergeIntersection(List1() As Long, List2() As Long, lOutput() As Long) As Boolean
  Dim l1 As Long, l2 As Long
  Dim lU1 As Long, lU2 As Long
  Dim lValue1 As Long, lValue2 As Long
  Dim lCnt As Long

  ' If 1 of the arrays is empty then the output is also empty
  If Not IsDimmed(List1) Then
    Erase lOutput
    Exit Function
  End If

  If Not IsDimmed(List2) Then
    Erase lOutput
    Exit Function
  End If

  lU1 = UBound(List1)
  lU2 = UBound(List2)

  ReDim lOutput(lU1)

  Do
    lValue1 = List1(l1)
    lValue2 = List2(l2)
    If lValue1 = lValue2 Then
      lOutput(lCnt) = lValue1
      lCnt = lCnt + 1
      l1 = l1 + 1
      l2 = l2 + 1
    ElseIf lValue1 > lValue2 Then
      l2 = l2 + 1
    Else
      l1 = l1 + 1
    End If
  Loop Until l1 > lU1 Or l2 > lU2

  If lCnt = 0 Then
    Erase lOutput
  Else
    ReDim Preserve lOutput(lCnt - 1)
    MergeIntersection = True
  End If
End Function

Private Function MergeUnion(List1() As Long, List2() As Long, lOutput() As Long) As Boolean
  Dim l1 As Long, l2 As Long
  Dim lU1 As Long, lU2 As Long
  Dim lValue1 As Long, lValue2 As Long
  Dim lCnt As Long, i As Long
  Dim bDimmed1 As Boolean, bDimmed2 As Boolean
  
  bDimmed1 = IsDimmed(List1)
  bDimmed2 = IsDimmed(List2)
  
  ' If both arrays are empty then the result is also empty
  If Not bDimmed1 And Not bDimmed2 Then
    Erase lOutput
    Exit Function
  End If

  If Not bDimmed1 Then
    lOutput = List2
    MergeUnion = True
    Exit Function
  End If
  
  If Not bDimmed2 Then
    lOutput = List1
    MergeUnion = True
    Exit Function
  End If

  lU1 = UBound(List1)
  lU2 = UBound(List2)

  ReDim lOutput(lU1 + lU2 + 1)

  lValue1 = List1(l1)
  lValue2 = List2(l2)

  Do
    If l1 > lU1 Then
      For i = l2 To lU2
        lValue2 = List2(i)
        If lValue2 <> lValue1 Then
          lOutput(lCnt) = lValue2
          lCnt = lCnt + 1
        End If
      Next i
      Exit Do
      
    ElseIf l2 > lU2 Then
      For i = l1 To lU1
        lValue1 = List1(i)
        If lValue1 <> lValue2 Then
          lOutput(lCnt) = lValue1
          lCnt = lCnt + 1
        End If
      Next i
      Exit Do
    
    Else
      If lValue1 = lValue2 Then
        lOutput(lCnt) = lValue1
        l1 = l1 + 1
        l2 = l2 + 1
        If l1 <= lU1 Then lValue1 = List1(l1)
        If l2 <= lU2 Then lValue2 = List2(l2)
      ElseIf lValue1 > lValue2 Then
        lOutput(lCnt) = lValue2
        l2 = l2 + 1
        If l2 <= lU2 Then lValue2 = List2(l2)
      Else
        lOutput(lCnt) = lValue1
        l1 = l1 + 1
        If l1 <= lU1 Then lValue1 = List1(l1)
      End If
      lCnt = lCnt + 1
    End If
  Loop Until l1 > lU1 And l2 > lU2

  If lCnt = 0 Then
    Erase lOutput
  Else
    ReDim Preserve lOutput(lCnt - 1)
    MergeUnion = True
  End If
End Function

' Code for dealing with BitVectors:

Public Sub VectorAND(bv1() As Long, bv2() As Long)
' Bitwise ANDs bv1 and bv2 together, and stores the result in bv1
  Dim indx As Long
  
  indx = UBound(bv1) + 1
  Do Until indx = 0
    indx = indx - 1
    bv1(indx) = bv1(indx) And bv2(indx)
  Loop
  
End Sub

Public Sub VectorOR(bv1() As Long, bv2() As Long)
' Bitwise ORs bv1 and bv2 together, and stores the result in bv1
  Dim indx As Long
  
  indx = UBound(bv1) + 1
  Do While indx <> 0
    indx = indx - 1
    bv1(indx) = bv1(indx) Or bv2(indx)
  Loop
End Sub

Public Sub VectorInvert(bv1() As Long)
' Invert bitvector array and stores the result in bv1
  Dim indx As Long
  
  indx = UBound(bv1) + 1
  Do While indx <> 0
    indx = indx - 1
    bv1(indx) = Not bv1(indx)
  Loop

End Sub

Public Function GetIndices(BitVector() As Long, lIndices() As Long) As Long
  Dim i As Long, ub As Long, lBV As Long
  Dim indx As Long, lBit As Long
  Dim lCnt As Long
  
  ub = UBound(BitVector)
  
  For indx = 0 To ub
    lBV = BitVector(indx)
    If lBV Then
      i = indx * 32&
      For lBit = 0 To 31
        If lBV And m_Bits(lBit) Then
          lIndices(lCnt) = i + lBit
          lCnt = lCnt + 1
        End If
      Next
    End If
  Next indx
  
  GetIndices = lCnt
End Function

Public Function IsDimmed(myArray As Variant) As Boolean
  On Error GoTo errHandler
  IsDimmed = UBound(myArray) >= LBound(myArray)

errHandler:
  ' obviously not dimensioned yet...
End Function

[Schmidt]

No it's not pre-generated data.
They are behavior statements.
Like watching TV or, some other dataset, internet behavior

That's what I assumed basically...

The huge uncompressed dataset comes from all the "index" tables.

So, there's (in addition to the "raw-data behaviour-statements" which
come in for a given day from your group of "research-respondents") -
also "artificially generated" Index-Data, which you then try to store as well...

I'm not sure, why you are doing all that indexing "by hand" (using your
own structures) - when there's DB-Engines which can ensure that
quite efficiently (well-optimized, and even InMemory)...

SQLite for example can do all that (including the Indexing) on your Raw-Data -
and it is (in your scenario) quite efficient even when storing your
"ID-Ranges"... (SQLite stores Integer-Data with an adaptive scheme,
which ensures that e.g. in a Column, containing only values from 0 to 99,
only "one Byte per Integer-Value" is used - and so on (dynamically) -
for signed Integers up to 64Bit - only using as many bytes as needed...).

The example below simplifies things quite a bit, but it uses an 'INET'-table
which it fills already with 150,000 "raw-records" - under the following assumptions:
- the Records consist of two fields, which are (in combination) unique over ActID, RespID
- ActID stands for a "visited WebSite" - RespID for the Respondent
- each respondent can have more than one record in the table (for different ActID-WebSite)
- the number of "unique Respondents" among the 150,000 records is limited to 40000
- the number of "unique ActID-WebSites" is limited to 5000

The uncompressed DB for the above scenario does have a final size
(including the Indexing over ActID, RespID) of 1.6MB (ZLib-compressed then ~0.8MB).

It will answer Search-Queries typically after only around 1msec (e.g. finding
all Records with a certain ActID).

Filling in the 150.000 Records of Raw-Data is done (including the Indexing)
at startup in about 330msec.

Here's the example (needs two Buttons: cmdTestPerformance and cmdSave on a Form)

Option Explicit

Private Cnn As cConnection

Private Sub Form_Load()
  Set Cnn = New_c.Connection(, DBCreateInMemory)
      Cnn.Execute "Create Table tInet(ActID Integer, RespID Integer, " & _
                                    "PRIMARY KEY (ActID, RespID) ) Without RowID"
  
  Dim Cmd As cCommand, i As Long
  Set Cmd = Cnn.CreateCommand("Insert Into tInet(RespID, ActID) Values(?,?)")
  
  New_c.Timing True
    Cnn.BeginTrans
      For i = 1 To 150000 '150000 reported site-visits from all the respondents
        Cmd.SetInt32 1, Rnd * 40000 'a range of max. 40000 unique resp. (each with multiple Site-visits)
        Cmd.SetInt32 2, Rnd * 5000  'a range of max. 5000 different WebSite-IDs
        Cmd.Execute
      Next
    Cnn.CommitTrans
  Caption = New_c.Timing
End Sub

Private Sub cmdTestPerformance_Click()
  'the way the Primary Key (ActID, RespID) was defined on the table, already ensures speedy queries over ActID
  New_c.Timing True
    Caption = Cnn.OpenRecordset("Select RespID From tInet Where ActID=2000").RecordCount
  Caption = Caption & New_c.Timing
End Sub

Private Sub cmdSave_Click()
Const DBName As String = "c:\temp\InetBehaviour.db3"
Dim B() As Byte
  If New_c.FSO.FileExists(DBName) Then New_c.FSO.DeleteFile DBName
  Cnn.CopyDatabase DBName
  New_c.Crypt.ZlibCompress New_c.FSO.ReadByteContent(DBName), B
  Caption = "DB-Size: " & Int(New_c.FSO.FileLen(DBName) / 1024) & "KByte, " & _
            "Compressed: " & Int((UBound(B) + 1) / 1024) & "KByte"
End Sub

I'd play around with that a bit (maybe adding a few more columns, to better match
a concrete set of your Raw-Data - perhaps reducing the amount of records
then from 150,000 to something "more common in daily use"...

Olaf

[Arnoutdv]

For the background variables, socio demographics, I do use a SQLite DB.
There are about 30 variables (age, gender, social class, area, etc etc)
And the values per respondent can change in time.
This for selecting the active respondents for creating a reporting group like "age 20-34 male"

For the day by day behavior data I've tried that solution too, but it really grew ridiculously.
With a minor problem, some fields are multivalue.
If the data was stored only on a huge DB server (like Hadoop) then I would put all data in single table and let the DB server do all the work, because most analysis require to process at least 1 month of data.
But this is a local PC solution, where data is sent to clients on daily basis.

I'll contact you privately if you don't mind about the performance and the size of a daily SQLite DB.
The data is quite sensitive.

[Schmidt]

I've tried that solution too, but it really grew ridiculously.
I'll contact you privately if you don't mind about the performance and the size of a daily SQLite DB.
The data is quite sensitive.

I can imagine that - but would like to find an efficient solution too ...
(your problem is quite interesting, you can also E-Mail me directly if you like).

Olaf

[Arnoutdv]

Additional results using ZSTD:

Library        Uncompressed  Zlib (CL=9)   ZSTD CL=1   ZSTD CL=5  ZSTD CL=10  ZSTD CL=14
4217 arrays     458,779,436    6,232,353   6,533,262   6,403,100   5,945,740   6,002,778 
                    437.5MB        5.9MB       6.2MB       6.1MB       5.7MB       5.7MB
                 Index ZLib         0.0%        4,8%        2,7%       -4,6%       -3,7%

These compression rates are quite on par with ZLib, now I have to compare the actual decompression speed on my dataset compared to ZLib.

Thanks wqweto for sharing your ZSTD library!

[wqweto]

So it look like ZSTD CL=1 is on par with zlib default CL (from vbRC) as compressed size but probably is 10x faster on compression in 2x on decompression.

Btw, the link above is a static build w/ VS2015 so it might not work anything less than Vista as it puts `Subsystem Version: 6.0` in PE header. VC6 builds use 4.0 for subsystem and work on NT4 and above.

I've sent the github project a pull request for stdcall builds w/ MSVC to become part of the project if they accept it, so it can be built w/ VC6 too.

Btw, now I notice that ZSTD is from the author of LZ4 and it seems like ZSTD CL=1 is like a next step in speed/size, a continuation from LZ4 CL=max.

cheers,
</wqw>

[Tanner_H]

Btw, the link above is a static build w/ VS2015 so it might not work anything less than Vista as it puts `Subsystem Version: 6.0` in PE header. VC6 builds use 4.0 for subsystem and work on NT4 and above.

VS 2015 will build XP-compatible DLLs if the Project Properties > General > Platform Toolset is set to Windows XP (v140_xp). I believe this option became available with a recent patch?? (Can't remember details, sorry - it's been awhile!)

Edit: XP support is discussed in this MSDN blog from July. Looks like you may need to reinstall the optional XP targeting features if you installed VS 2015 prior to that point.

[wqweto]

Adding /subsystem:windows,5.1 to linker options did the trick. Obviously 6.0 is just a default value for /subsystem option in VS2015 but not the minimum supported.

Thanks for the hint.

cheers,
</wqw>

[Arnoutdv]

Just read an update about Zstandard an improved compression method by the developers of Facebook.
Compression very scaleable between speed and size, decompression is extremely fast.
https://code.facebook.com/posts/1658...ith-zstandard/

I did some small tests with command-line tool and the results are very promising!
https://github.com/facebook/zstd/releases

[Arnoutdv]

The only resource I could find for VB6 is still the same as already compiled and posted by wqweto in post #20 of this thread.

[wqweto]

https://github.com/facebook/zstd/pull/166

My PR for stdcall binding was dismissed as too disruptive as at that time they were making some large changes to the core of the library.

Doubt this PR can be rebased on 1.0 release as is because public interface has been changed a lot and my incentive to revise it is not very high provided it got previously rejected as not very useful.

cheers,
</wqw>

[Arnoutdv]

I read through it, quite disappointing

[wqweto]

https://github.com/wqweto/zstd/releases

Here is a rebuild of the original stdcall modifications on current v1.0 thrunk.

Binaries compiled with VS2015 with `Operating System Version: 5.1` targeting Win XP and above.

Enjoy!
</wqw>

[Arnoutdv]

I will check it out!