Pull request: hashtable bag count template parameter

[freddyhayward]

This patch (https://github.com/jamespetts/simutrans-extended/pull/330) delivers at least 3 GB of saved memory consumption for bridgewater-brunel. It does this by changing the bag count of certain hashtables, most importantly the private car route maps, based on the expected number of tables and expected number of elements per table. From my tests, it does have a slight adverse effect on loading and saving on bridgewater-brunel on my machine, but this should not prevent this pull request from being merged because:
1. bridgewater-brunel is the only known active game where save/load times are an issue and its current bottleneck is memory usage and swap space, so tests on my machine with double the available memory are not applicable. The server game will therefore probably see an enormous reduction in load/save times because of the reduction in memory usage.
2. The bag sizes of different hashtables can easily be changed again via the template arguments after further testing and discussion.
I highly recommend that this pull request is merged as soon as possible, as even in its current state, the positives overwhelmingly outweigh any negatives.

[jamespetts]

Thank you very much for this.

A preliminary question at this juncture: may I ask why the path explorer's bag sizes have been set to small? Was there any testing that informed this decision? The path explorer's various hashtables only exist once each, so reducing the memory overhead for each of these hashtables will save only a few kilobytes in total, and I suspect that the largest performance impact may well be from the path explorer hashtables having their bag size reduced, but this will need to be tested.

However, such a large reduction in memory consumption is a very impressive thing to have achieved: thank you for this work.

[freddyhayward]

A preliminary question at this juncture: may I ask why the path explorer's bag sizes have been set to small? Was there any testing that informed this decision? The path explorer's various hashtables only exist once each, so reducing the memory overhead for each of these hashtables will save only a few kilobytes in total, and I suspect that the largest performance impact may well be from the path explorer hashtables having their bag size reduced, but this will need to be tested.

This was mainly guesswork - I couldn't determine the number of hashtables for the path explorer myself, so thank you for pointing this out. If there are only a few hashtables for the path explorer, they should absolutely be set to the large number of bags (i.e. the default before this change) - or possibly even higher if it improves performance. If you can identify any other bag counts set too low, please let me know.
edit: could you please point out which tables in the path explorer only exist in a few instances? Some of them appear to be contained in a list of 65536.

[jamespetts]

Thank you for your reply: that is helpful. Analysing all of the path explorer hashtables one by one, we have:

(1)

Code Select Expand


// an array for keeping a list of connexion hash table
static connexion_list_entry_t connexion_list[65536];


There appear to be 65535 instances of connexion_list.

(2)

Code Select Expand


vector_tpl<connection_cluster_t*> connection_clusters;
uint32 usage_level; // number of connection clusters used
uint32 halt_vector_size; // size of connected halt vector in connection cluster object
typedef  inthashtable_tpl<uint16, connection_cluster_t*, N_BAGS_SMALL> cluster_map_type;
cluster_map_type cluster_map;


There appears to be only the one instance of cluster_map.


I am not quite sure how much that reducing the number of bags will save for 65536 entries, but certainly cluster_map should have N_BAGS_LARGE, I think.

[freddyhayward]

I am not quite sure how much that reducing the number of bags will save for 65536 entries, but certainly cluster_map should have N_BAGS_LARGE, I think.

Reducing the bag count of 65536 hashtables from 101 to 11 reduces overhead consumption by ~160MB. That is a substantial amount but an order of magnitude less than doing the same for private car routes. If these tables are especially performance-critical and have hundreds or thousands of elements each, then it may be well worth forgoing that saving. Alternatively, reducing the size to N_BAGS_MEDIUM (37) would reduce memory consumption by ~120MB.

[jamespetts]

Thank you for this. I have tried this on Linux, but unfortunately I get an error on loading demo.sve:

Code Select Expand


Warning: karte_t::load: File version: 120004, Extended version: 12, Extended revision: 21
simutrans-extended: malloc.c:2379: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)


[freddyhayward]

Thank you for this. I have tried this on Linux, but unfortunately I get an error on loading demo.sve:

Code Select Expand


Warning: karte_t::load: File version: 120004, Extended version: 12, Extended revision: 21
simutrans-extended: malloc.c:2379: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)


I haven't been able to reproduce this. Do you get the same issue when running newer saves, or with the latest master build?

[jamespetts]

I haven't been able to reproduce this. Do you get the same issue when running newer saves, or with the latest master build?

I do not get this problem at all with the code that I compile from the master branch. The problem did occur initially when loading a newer save, as it would have attempted to load the game that was saved automatically when it last closed, a modified version of demo.sve that I had used for testing.

Are you trying to reproduce this on Linux or Windows?

Edit: I see from the Discord channel that you are using Linux. Can I check exactly what code that you were testing; when I tested this, I merged code from your branch into the current master branch. Is that exactly what you have done, or is your branch based on an older version of the code?

[freddyhayward]

Edit: I see from the Discord channel that you are using Linux. Can I check exactly what code that you were testing; when I tested this, I merged code from your branch into the current master branch. Is that exactly what you have done, or is your branch based on an older version of the code?

My branch is based on the current master branch, so there shouldn't be any difference here.

[jamespetts]

My branch is based on the current master branch, so there shouldn't be any difference here.

That is very odd - it was from the master branch that I merged your branch and produced the binary that gave these errors. However, running your binary from the Discord channel does not seem to give these errors, so something very odd is happening.

[freddyhayward]

That is very odd - it was from the master branch that I merged your branch and produced the binary that gave these errors. However, running your binary from the Discord channel does not seem to give these errors, so something very odd is happening.

can you try checking out my branch directly and compiling from there without any merging? It shouldn't make any difference, but it may.

[jamespetts]

I will try that shortly; but in the meantime, can I check your compile settings in config.default, incidentally? Mine are as follows:

Code Select Expand

#
# This file is part of the Simutrans-Extended project under the Artistic License.
# (see LICENSE.txt)
#

#
# to compile:
# copy this file to config.default and adjust the settings
#

#BACKEND = gdi
#BACKEND = sdl
BACKEND = sdl2
#BACKEND = mixer_sdl
#BACKEND = posix

#COLOUR_DEPTH = 0
COLOUR_DEPTH = 16

#OSTYPE = amiga
#OSTYPE = beos
#OSTYPE = cygwin
#OSTYPE = freebsd
#OSTYPE = haiku
OSTYPE = linux
#OSTYPE = mingw32
#OSTYPE = mingw64
#OSTYPE = mac
#OSTYPE = openbsd

#DEBUG = 1    # Level 1-3, higher number means more debug-friendly but slower, see Makefile
#MSG_LEVEL = 1 # Level 1-4, more runtime debug messages (without only warnings and errors)
OPTIMISE = 1 # Add umpteen optimisation flags
#PROFILE = 1  # Enable profiling
#PROFILE = 2  # Enable profiling with optimisation flags, can be used with `OPTIMISE = 1'

#AV_FOUNDATION = 1  # Use AVFoundation instead of QTKit. If you are using macOS 10.12 or later, this must be enabled.

WITH_REVISION = 1 # adds the commit number (truncated) from Github; important for network games
# if you do not use Github and the related scripts for setting the commit number automatically, add -DREVISION="1234" to the FLAGS below

#WIN32_CONSOLE = 1 # adds a console for windows debugging

MULTI_THREAD = 1 # Enable multithreading

# using freetype for Truetype font support
#USE_FREETYPE = 1

# using UPnP for easy server hosting behind routers
#USE_UPNP = 0

# using zstd compression library
USE_ZSTD = 1

# Define these as empty strings, if you don't have the respective config program
PNG_CONFIG     = pkg-config libpng
#SDL_CONFIG     = sdl-config
SDL2_CONFIG    = sdl2-config
FREETYPE_CONFIG = freetype-config

#VERBOSE = 1

# The following useful conditional compilation flags exist
#
# Needed to compile:
# USE_C: no assembler for copying (required for not using GCC on x86)
# SIM_BIG_ENDIAN: MUST be set for PPC/Motorola byte order! (old mac, amiga)
# NO_INTPTR_T: must be set if intptr_t is not available
#
# Changing appearance:
# USE_SOFTPOINTER: emulate mouse pointer (set automatically in Makefile)
#
# Useful for debugging:
# DEBUG_ROUTES: show routing calculation information in minimap
# SHOW_FORE_GRUND: show which objects are drawn as foreground
# DEBUG_FLUSH_BUFFER: show the dirty areas on the screen
# USE_VALGRIND_MEMCHECK: make valgrind-memcheck aware of the memory allocation stuff in dataobj/freelist
# SYSLOG: send debug output to syslog
#
# Following flags alter game engine (and are off for standard builds)
# OTTD_LIKE: Enables half height tiles and crossconnects all industries
# AUTOMATIC_BRIDGES and AUTOMATIC_TUNNELS: will be built also for player
# AUTOJOIN_PUBLIC: stations next to a public stop will be joined to it
# USE_DIFFERENT_WIND: different airplane approach directions over the map
#
# In order to use the flags, add a line like this: (-Dxxx)
# FLAGS = -DUSE_C
# The above flag is recommended for speed on modern CPUs: see http://forum.simutrans.com/index.php?topic=16773.msg159658#msg159658

# Output directories:
#
# use this put objects file in same directory, where the sources are (not recommended):
# ... otherwise defaults to 'build/default')
#
BUILDDIR = simutrans
#
# use this to specify the target directory for the executable:
# .. otherwise defaults to BUILDDIR
#
#MAKEOBJ_PROGDIR = ../simutrans-pak128.britain
NETTOOL_PROGDIR = simutrans
PROGDIR  = simutrans

# For compiling on Linux with SDL2, use -I/usr/include/SDL2
# For compiling on Linux with Freetype 2, use -I/usr/include/freetype2
# For compiling on Linux with miniupnpc, use -I/usr/includeude/miniupnpc
FLAGS = -DUSE_C -fno-delete-null-pointer-checks -fno-strict-aliasing -std=c++11 -I/usr/include/freetype2

# This library does not seem to exist - but where are the freetype2 libraries, in that case?
#LDFLAGS = -L/usr/lib/freetype2
Edit: I have tried checking out the bag_count_parameter branch directly, and I still get the same error on attempting to run Simutrans-Extended:

Code Select Expand

Calculating textures ...done
Warning: karte_t::load:    File version: 120007, Extended version: 14, Extended revision: 32
simutrans-extended: malloc.c:2379: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)


[freddyhayward]

I will try that shortly; but in the meantime, can I check your compile settings in config.default, incidentally? Mine are as follows:

Code Select Expand

#
# This file is part of the Simutrans-Extended project under the Artistic License.
# (see LICENSE.txt)
#

#
# to compile:
# copy this file to config.default and adjust the settings
#

#BACKEND = gdi
#BACKEND = sdl
BACKEND = sdl2
#BACKEND = mixer_sdl
#BACKEND = posix

#COLOUR_DEPTH = 0
COLOUR_DEPTH = 16

#OSTYPE = amiga
#OSTYPE = beos
#OSTYPE = cygwin
#OSTYPE = freebsd
#OSTYPE = haiku
OSTYPE = linux
#OSTYPE = mingw32
#OSTYPE = mingw64
#OSTYPE = mac
#OSTYPE = openbsd

#DEBUG = 1    # Level 1-3, higher number means more debug-friendly but slower, see Makefile
#MSG_LEVEL = 1 # Level 1-4, more runtime debug messages (without only warnings and errors)
OPTIMISE = 1 # Add umpteen optimisation flags
#PROFILE = 1  # Enable profiling
#PROFILE = 2  # Enable profiling with optimisation flags, can be used with `OPTIMISE = 1'

#AV_FOUNDATION = 1  # Use AVFoundation instead of QTKit. If you are using macOS 10.12 or later, this must be enabled.

WITH_REVISION = 1 # adds the commit number (truncated) from Github; important for network games
# if you do not use Github and the related scripts for setting the commit number automatically, add -DREVISION="1234" to the FLAGS below

#WIN32_CONSOLE = 1 # adds a console for windows debugging

MULTI_THREAD = 1 # Enable multithreading

# using freetype for Truetype font support
#USE_FREETYPE = 1

# using UPnP for easy server hosting behind routers
#USE_UPNP = 0

# using zstd compression library
USE_ZSTD = 1

# Define these as empty strings, if you don't have the respective config program
PNG_CONFIG     = pkg-config libpng
#SDL_CONFIG     = sdl-config
SDL2_CONFIG    = sdl2-config
FREETYPE_CONFIG = freetype-config

#VERBOSE = 1

# The following useful conditional compilation flags exist
#
# Needed to compile:
# USE_C: no assembler for copying (required for not using GCC on x86)
# SIM_BIG_ENDIAN: MUST be set for PPC/Motorola byte order! (old mac, amiga)
# NO_INTPTR_T: must be set if intptr_t is not available
#
# Changing appearance:
# USE_SOFTPOINTER: emulate mouse pointer (set automatically in Makefile)
#
# Useful for debugging:
# DEBUG_ROUTES: show routing calculation information in minimap
# SHOW_FORE_GRUND: show which objects are drawn as foreground
# DEBUG_FLUSH_BUFFER: show the dirty areas on the screen
# USE_VALGRIND_MEMCHECK: make valgrind-memcheck aware of the memory allocation stuff in dataobj/freelist
# SYSLOG: send debug output to syslog
#
# Following flags alter game engine (and are off for standard builds)
# OTTD_LIKE: Enables half height tiles and crossconnects all industries
# AUTOMATIC_BRIDGES and AUTOMATIC_TUNNELS: will be built also for player
# AUTOJOIN_PUBLIC: stations next to a public stop will be joined to it
# USE_DIFFERENT_WIND: different airplane approach directions over the map
#
# In order to use the flags, add a line like this: (-Dxxx)
# FLAGS = -DUSE_C
# The above flag is recommended for speed on modern CPUs: see http://forum.simutrans.com/index.php?topic=16773.msg159658#msg159658

# Output directories:
#
# use this put objects file in same directory, where the sources are (not recommended):
# ... otherwise defaults to 'build/default')
#
BUILDDIR = simutrans
#
# use this to specify the target directory for the executable:
# .. otherwise defaults to BUILDDIR
#
#MAKEOBJ_PROGDIR = ../simutrans-pak128.britain
NETTOOL_PROGDIR = simutrans
PROGDIR  = simutrans

# For compiling on Linux with SDL2, use -I/usr/include/SDL2
# For compiling on Linux with Freetype 2, use -I/usr/include/freetype2
# For compiling on Linux with miniupnpc, use -I/usr/includeude/miniupnpc
FLAGS = -DUSE_C -fno-delete-null-pointer-checks -fno-strict-aliasing -std=c++11 -I/usr/include/freetype2

# This library does not seem to exist - but where are the freetype2 libraries, in that case?
#LDFLAGS = -L/usr/lib/freetype2

Note that I usually use CMake, but also tested using regular make:

Code Select Expand

#
# to compile:
# copy this file to config.default and adjust the settings
#

#BACKEND = allegro
#BACKEND = gdi
#BACKEND = opengl
#BACKEND = sdl
BACKEND = sdl2
#BACKEND = mixer_sdl
#BACKEND = posix

#COLOUR_DEPTH = 0
COLOUR_DEPTH = 16

#OSTYPE = amiga
#OSTYPE = beos
#OSTYPE = cygwin
#OSTYPE = freebsd
#OSTYPE = haiku
OSTYPE = linux
#OSTYPE = mingw32
#OSTYPE = mingw64
#OSTYPE = mac
#OSTYPE = openbsd

#DEBUG = 3    # Level 1-3, higher number means more debug-friendly but slower, see Makefile
#MSG_LEVEL = 4 # Level 1-4, more runtime debug messages (without only warnings and errors)
OPTIMISE = 1 # Add umpteen optimisation flags
#PROFILE = 1  # Enable profiling
#PROFILE = 2  # Enable profiling with optimisation flags, can be used with `OPTIMISE = 1'

WITH_REVISION = 1 # adds the commit number (truncated) from Github; important for network games
# if you do not use Github and the related scripts for setting the commit number automatically, add -DREVISION="1234" to the FLAGS below

#WIN32_CONSOLE = 1 # adds a console for windows debugging

MULTI_THREAD = 1 # Enable multithreading

#AV_FOUNDATION = 1  # Use AVFoundation instead of QTKit. If you are using macOS 10.12 or later, this must be enabled.

# Define these as empty strings, if you don't have the respective config program
ALLEGRO_CONFIG = allegro-config
PNG_CONFIG     = pkg-config libpng
SDL_CONFIG     = sdl-config
SDL2_CONFIG    = sdl2-config

#VERBOSE = 1

# The following useful conditional compilation flags exist
#
# Needed to compile:
# USE_C: no assembler for copying (required for not using GCC on x86)
# SIM_BIG_ENDIAN: MUST be set for PPC/Motorola byte order! (old mac, amiga)
# NO_INTPTR_T: must be set if intptr_t is not available
#
# Changing appearance:
# USE_SOFTPOINTER: emulate mouse pointer (set automatically in Makefile)
#
# Useful for debugging:
# DEBUG_ROUTES: show routing calculation information in minimap
# SHOW_FORE_GRUND: show which objects are drawn as foreground
# DEBUG_FLUSH_BUFFER: show the dirty areas on the screen
# USE_VALGRIND_MEMCHECK: make valgrind-memcheck aware of the memory allocation stuff in dataobj/freelist
# SYSLOG: send debug output to syslog
#
# Following flags alter game engine (and are off for standard builds)
# OTTD_LIKE: Enables half height tiles and crossconnects all industries
# AUTOMATIC_BRIDGES and AUTOMATIC_TUNNELS: will be built also for player
# AUTOJOIN_PUBLIC: stations next to a public stop will be joined to it
# USE_DIFFERENT_WIND: different airplane approach directions over the map
# DESTINATION_CITYCARS: Citycars can have a destination (enabled automatically - cannot be disabled)
#
# In order to use the flags, add a line like this: (-Dxxx)
# FLAGS = -DUSE_C
# The above flag is recommended for speed on modern CPUs: see http://forum.simutrans.com/index.php?topic=16773.msg159658#msg159658

# Output directories:
#
# use this put objects file in same directory, where the sources are (not recommended):
# ... otherwise defaults to 'build/default')
#
# BUILDDIR = $(shell pwd)
#
# use this to specify the target directory for the executable:
# .. otherwise defaults to BUILDDIR
#
# MAKEOBJ_PROGDIR = $(shell pwd)
# NETTOOL_PROGDIR = $(shell pwd)
# PROGDIR  = $(shell pwd)

FLAGS = -DUSE_C -fno-delete-null-pointer-checks -fno-strict-aliasing -std=c++11


[jamespetts]

I notice that your build is not set up for zstd; can I ask you to re-test with the config.default that I use?

[freddyhayward]

I notice that your build is not set up for zstd; can I ask you to re-test with the config.default that I use?

I have re-tested using that config without any problems.

[jamespetts]

I have re-tested using that config without any problems.

Very odd. Might it be something to do with libraries, I wonder? Are you also using Ubuntu 20.04.1 LTS?
Incidentally, the executable that you provided worked well enough to allow me to connect to the Bridgewater-Brunel server and do some work on the public road network there. The game took only 5.5GiB on my portable Linux computer (which, having only 8GiB total RAM, is usually unable to run the Bridgewater-Brunel game at all). Performance seemed acceptable and not noticeably different from the ordinary version.
If we can fix this compilation problem, this should be a very helpful patch to integrate.

[freddyhayward]

Very odd. Might it be something to do with libraries, I wonder? Are you also using Ubuntu 20.04.1 LTS?

Yes I am. Could you try creating a debug build? Additionally, could you upload your non-working builds either here or on discord so that I can test whether it produces the same error on my machine?

[jamespetts]

I think that I have tracked down the issue, which was at my end: it seems that the error only occurs when I fail to run "make clean" after building from the latest master branch before building the merged version. Having done that, it now works well. I am about to integrate this into the master branch now. Thank you very much for your work on this.

[Matthew]

Today I gave a Linux executable with this patch a very basic test: running an offline Bridgewater-Brunel save unattended for three-quarters of an hour at normal speed, then on fast-forward for ten minutes so that I could watch it cross a month boundary. Nothing unexpected happened . The game used 5.5GiB of RAM at load and about 7.3GiB when I exited, which is within the typical range of variation for B-B, and is a vast improvement.

Thank you Freddy for writing the code, Freahk for advising, and James for code review!

[Mariculous]

Oh, I really didn't do much. You're welcome nevertheless.

This improvement seems quite worth it. Good job and thanks a lot.

[jamespetts]

This has now deployed on the server. Testing with my memory limited machine, I am able to log into the server game, although I ran out of memory shortly after connecting. However, the "server preparing game" state lasted for a shorter time than when I tried yesterday, as did the pause after loading; the longest period was now the transferring the saved game file.

Looking now, with 2 clients connected, memory usage is reported as 70.4% and CPU usage 71.3%. This seems to be a significant improvement, I think. Thanks again to Freddy for his excellent work on this.